算法删除链表的倒数第N个节点(php&golang)

Z时代
2024-01-10
分类：综合

//给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
//链表节点
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) { $this->val = $val; }
}
//生成单链表
class SingleLinkedList
{
    public $head;
    public function __construct($head = null)
    {
        if ($head == null) {
            $this->head = new ListNode(0);
        } else {
            $this->head = $head;
        }
    }
    public function insert($data)
    {
        $h = $this->head;
        $newNode = new ListNode($data);
        $newNode->next = $h->next;
        $h->next = $newNode;
        return $newNode;
    }
   //思路依赖快慢指针,增加哨兵节点
    public function removeNthFromEnd($head, $n)
    {
        $dummy = new ListNode(0);//加上了头节点，相当于是哨兵，可以简化操作
        $dummy->next = $head;
        $slow = $dummy;
        $fast = $dummy;
        //快指针走到距离慢指针n+1位置时(慢指针的父节点位置)
        for ($i=0; $i < $n+1; $i++) {
            $fast = $fast->next;
        }
        //快指针走到结尾 慢指针正好走到n+1的位置 然后 取n+1的下一个节点删除
        while ($fast) {
            $fast = $fast->next;
            $slow = $slow->next;
        }
        $delNode = $slow->next;
        $slow->next = $delNode->next;
        unset($delNode);
        return $dummy->next;
    }
}
$s = new SingleLinkedList();
$s->insert(5);
$s->insert(4);
$s->insert(3);
$s->insert(2);
$s->insert(1);
var_dump($s->removeNthFromEnd($s->head->next, 2));