leetCode 刷题 算法入门20天（四）

题目链接： 876. 链表的中间结点

解题思路：比较简单，快慢指针；p，q两个指针；初始p，q指向头结点；p每次移动1位，q每次移动2位；当q访问到链表尾部时，p刚好到链表中间；

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        //快慢指针 p每次前进一个位置，q每次前进两个位置
        ListNode *p=head,*q=head;
        while(q->next!=NULL){
            p = p->next;
            q = q->next;
            if(q->next==NULL)
                break;
            else
                q = q->next;
        }
        return p;
    }
};

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 

解题思路：双指针法，让一个指针q先向后移动n-1个,此时该指针与头结点的距离为n，此时同时让两个指针p，q向后移动，同时用pre指针记录p的前驱，方便删除p，当q移动到链表尾部时，p的位置即为需要删除的倒数第n个节点。需要注意的是，如果q向后移动n个位置后，恰好到达最后一个节点，则此时头结点即为需要删除的节点，这是由于p，pre初始时均指向头结点，所以可以根据pre和p是否相等来判断p是否移动。

代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p = head,*q = head,*pre=head;
        //q向前移动n-1个位置,此时p，q之间相距为n
        while(q->next!=NULL&&n-1>0){
            q = q->next;
            n--;
        }
        //q向后移动至链表尾部，同时p先前移动相同长度，保持p，q之间的距离为n,pre记录p的前驱
        while(q->next!=NULL){
            pre = p;
            p=p->next;
            q=q->next;
        }
        //此时p即为倒数第n个节点；
        // 如果pre和p指向同一个节点，则p并未向后移动，第一个节点为需要删除的节点
        if(pre == p)
             head = head->next;
        else{
            pre->next = p->next; 
        } 
        return head;
    }
};

https://www.cnblogs.com/downey-blog/p/10471875.html  c++STL 哈希表