数据结构-线性表(数组)-双指针-快慢指针 Offer22&19

1. 剑指 Offer 22. 链表中倒数第k个节点

2. 删除链表的倒数第 N 个结点

• 思路
  对链表操作时，为了首尾节点操作与其他节点相同，需要添加头节点(哑节点dummy node)。

1. 先确定链表的长度，然后找到要删除节点的前驱节点，进行删除。需要添加哑节点
2. 双指针(快慢指针)：快指针比慢指针快n+1个，因为慢指针要指向被删除元素的前驱节点，遍历整个链表，当快指针指向空时，慢指针正好指向被删除节点的前驱节点。初始化慢指针指向哑节点，快指针指向链表第一个节点
3. 栈

• 代码
  第一个方法;

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy  = new ListNode(0,head);
        ListNode* low = dummy;
        ListNode* res = nullptr;
        int len = 0;;
        while(head){
            ++len;
            head = head->next;
        }
        for(int i = 0;i
            low = low->next;
        }
        low->next = low->next->next;
        res = dummy->next;
        return res;
    }

快慢指针;

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy  = new ListNode(0,head);
        ListNode* low = dummy;
        ListNode* fast = head;
        ListNode* res = nullptr;
        int i = 0;
        while(i
            ++i;
            fast = fast->next;
        }
        while(fast){
            low = low->next;
            fast = fast->next;
        }
        low->next = low->next->next;
        res = dummy->next;
        return res;
    }

• 总结
  1：对列表操作为了首节点操作不失一般性，需要添加哑节点
  2：链表确定长度
  3：删除链表某个节点 p->next = p->next->next; 不一定非要找到指向被删除节点的下一个节点的指针p1使p->next = p1;