算法第五天 双指针

完成日期：7月13日
今日总结：

1. 指针：注意.和->的使用，有指针想想是不是用->，没指针就用.
2. 涉及到链表节点删除情况，要考虑头节点被删除，一般引入额外头节点

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

// 很容易想到第一次行头到尾遍历链表算长度，第二次从头到尾遍历到答案所在位置

// 然后又想到了第二种，使用快慢双指针，一个走一步，一个走两步

ListNode* middleNode(ListNode* head) {
        ListNode* slow=head, *fast=head;
        while(fast!=nullptr && fast->next!=nullptr){  // 记得判断两个节点
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？

// 同样是快慢指针，但是注意，链表的删除考虑删除表头的情况。
// 最好引入额外新表头
ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *pre_head=new ListNode(0, head);
        ListNode *slow=pre_head, *fast=pre_head;
        while(fast!=nullptr && n--){
            fast=fast->next;
        }
        while(fast->next!=nullptr){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return pre_head->next;
    }

// 还有一种栈方法，记录下遍历过的节点，就单指针遍历，但消耗内存多