更好的阅读体验

前言

本次的链表分享整理主要分了上、中、下三部分。<上>主要是求给定链表的一些性质，如倒数第k个节点，是否有环等。<中>主要包括链表的一些操作类问题，如反转、旋转、删除、归并、排序等。<下>的内容相对来说杂一些，包括一些设计类的题目，还有与其他数据结构之间的转化等。

双指针、哈希表是解决链表问题的不二利器，会根据不同类型的题目来慢慢体会着两种思想是如何应用的，还有常见的如哑铃头节点（dummy）的妙用。

下面就正式进入<上>的内容

一、 输出特定位置节点的值

（1）位置为中间结点

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

思路 [快慢双指针]

快慢指针同时走，快的走两步，慢的走一步。

等快指针走到尾节点时，慢指针便指向了中间结点。

细节

如何判断快指针抵达尾节点？

while(fast && fast-> next) 两个条件缺一不可

c++ 代码

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast-> next){  // 这里条件很重要
            slow = slow -> next;
            fast = fast -> next -> next;
        }

        return slow;
    }
};

（2）位置为倒数第k个节点

题目链接 面试题 02.02. 返回倒数第 k 个节点

思路

朴素的想法是求出链表的长度。不放设其长度为 L, 那么倒数第k个节点便为正数第L - k + 1个，但这样会遍历两次。

利用快慢双指针，让快的先走k步,然后快慢一起走，直到快指针走到

• 尾节点 , 此时慢指针指向倒数第k +1个结点
• 空节点 , 此时慢指针指向倒数第k个结点

细节

有无虚拟头结点的区别

无论有无虚拟头节点，按照规则“行走”，快指针走向尾节点 , 此时慢指针指向倒数第k +1个结点，若指向空节点 , 此时慢指针指向倒数第k个结点。

有虚拟头节点可以确保快指针先走k步后，一定不会指向空节点

c++代码

1) 没有虚拟头结点

//.................快指针指向空节点...............................//

class Solution {
public:
  int kthToLast(ListNode* head, int k) {
    ListNode *first = head;
    ListNode *second = head;

    while(k--) first = first -> next;

    while(first)
    {
      first = first -> next;
      second = second -> next;
    }

    // 此时second 即为倒数第N个节点
    return second -> val;
  }
};


//.................快指针指向尾节点...............................//
class Solution {
public:
  int kthToLast(ListNode* head, int k) {
    ListNode *first = head;
    ListNode *second = head;

    while(k --) first = first -> next;

    if(first == nullptr) return head -> val;

    while(first -> next)
    {
      first = first -> next;
      second = second -> next;
    }
    // 此时second 即为倒数第N+1个节点
    return second -> next -> val;
  }

};

2）有虚拟头结点

//.................快指针指向空节点...............................//

class Solution {
public:
  int kthToLast(ListNode* head, int k) {
    ListNode *dummy = new ListNode(-1);
    dummy -> next = head;

    ListNode *first = dummy;
    ListNode *second = dummy;

    while(k --) first = first -> next;  

    while(first)
    {
      first = first -> next;
      second = second -> next;
    }
    return second -> val;
  }

};


//.................快指针指向尾节点...............................//

class Solution {

public:

  int kthToLast(ListNode* head, int k) {
    ListNode *dummy = new ListNode(-1);
    dummy -> next = head;
    ListNode *first = dummy;
    ListNode *second = dummy;

    while(k --) first = first -> next;
    // 有了虚拟头结点不用对first判空 
    while(first -> next)
    {
      first = first -> next;
      second = second -> next;
    } 
    return second -> next -> val;
  }

};

二、判断给定链表的性质

（1） 是否有环

题目链接 141. 环形链表

思路

1）哈希表

遍历节点的过程中判断该节点之前有没有出现过，若出现过则有环

2）双指针

快慢双指针，快走2步，慢走一步，如果相遇则有环

c++代码

1) 哈希表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        map<ListNode*,int> hash;
        ListNode* p = head;
        while(p)
        {
            if(hash[p]>1)
                return true;
            else
                hash[p]++;

            p = p->next; 
        }
        return false; 
    }
};

2) 双指针

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        // 快慢指针 
        while (fast && fast -> next)
        {
            slow = slow -> next;
            fast = fast -> next -> next;
            // 能相遇 说明有环 
            if (slow == fast) 
                return true;

        } 
        return false;
    }
};

（2）是否有环，若有返回环的入口节点

题目链接 面试题 02.08. 环路检测 | 142. 环形链表 II

思路

快慢双指针判断是否有环

若有环，快指针指向头节点后，快慢指针一起走，直到二者再次相遇。

c++代码

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        // 快慢指针 
        while (fast && fast -> next)
        {
            slow = slow -> next;
            fast = fast -> next -> next;

            if (slow == fast) 
            {
                fast = head;
                while (slow != fast)
                {
                    slow = slow -> next;
                    fast = fast -> next;
                }
                return slow;
            }
        } 
        return nullptr;

    }
};

（3）是否回文

题目链接 面试题 02.06. 回文链表

思路

快慢双指针找到中间结点，把链表分为前后两部分

反转后半部分后，依次比较对应位置是否相同

反转操作放在<中>详细讲解。

反转就是将其next指向其前继，而单链表无法直接获取其前继，所以需要一个变量来保存。

修改单链表的next指针时记得保存原来的后继

c++代码

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head, *fast = head,*prev = nullptr;

        //快慢指针找中间结点
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //翻转后面的结点 因为单链表只能从前给后遍历 
        while(slow){
            ListNode* temp = slow->next;
            slow->next = prev;
            prev = slow;
            slow = temp;
        }

        //依次遍历 比较大小
        while(head && prev){
            if(head->val != prev->val) 
                return false;
            head = head->next;
            prev = prev->next;
        }

        return true;

    }
};

（4）是否相交

题目链接 160. 相交链表

思路

双指针遍历，若到该链表的末尾，则指向另外一个链表的头。

若相交，则返回的是相交的节点，不相交，返回的是空指针(其实也算特殊的相交)

c++代码

   ListNode* p = headA;
        ListNode* q = headB;

        while(p != q)  
        {
            if(p) p=p->next;
            else  p=headB;

            if(q) q=q->next;
            else  q=headA;
        }
        // 此时 p == q ; 可能是空指针；可能是相交的节点
        return  p ;

小结

想到双指针，要想到

• 指针的初始化
• 指针之间的运动关系是什么？
• 结束状态指针指的是谁？有什么意义？

下次的分享就是操作类集合了~