目录

 

141. Linked List Cycle

142. Linked List Cycle II

876. Middle of the Linked List

160. Intersection of Two Linked Lists

21. Merge Two Sorted Lists

23. Merge k Sorted Lists

206. Reverse Linked List

234. Palindrome Linked List

92. Reverse Linked List II

25. Reverse Nodes in k-Group

19. Remove Nth Node From End of List

24. Swap Nodes in Pairs

2. Add Two Numbers

---

相遇的角度思考

141. Linked List Cycle

Linked List Cycle - LeetCode

相遇则且不为NULL则说明存在环

 bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && slow){
            slow = slow->next;
            fast = fast->next;
            if(fast)    fast = fast->next;
            if(slow==fast && fast!=NULL)    return true;
        }
        return false;
    }

142. Linked List Cycle II

Linked List Cycle II - LeetCode

推导思路：

 ListNode *detectCycle(ListNode *head) {
        
        ListNode* fast = head;
        ListNode* slow = head;
        while(slow && fast){
            slow = slow->next;
            fast= fast->next;
            if(fast)    fast = fast->next;
            
            if(slow==fast && slow!=NULL)//相遇——存在环
            {
                fast = head;
                break;
            }
        }
        while(slow && fast){
            if(slow==fast)  return slow;
            slow = slow->next;
            fast = fast->next;
           
        }
        return NULL;
    }

876. Middle of the Linked List

Middle of the Linked List - LeetCode

    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next){
            fast = fast->next;
            if(fast) fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }

主动构造环

287. Find the Duplicate Number

(3) Find the Duplicate Number - LeetCode

利用位置与哈希的思想主动构造环：

 这就变成了双指针相遇找环的问题

160. Intersection of Two Linked Lists

Intersection of Two Linked Lists - LeetCode

解法一：利用两链长度不同交替遍历

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pAB = headA;
        ListNode* pBA = headB;
        while(pAB!=pBA){
            if(pAB==NULL)
                pAB = headB;
            else pAB = pAB->next;
            if(pBA==NULL)
                pBA = headA;
            else pBA = pBA->next;
        } 
        return pAB;
    }

解法二：借用环的思路

把其中一条链表首尾相连，若存在公共链则转换为寻找环起点，若不存在环起点则无公共链

解法三：先获得两链的长度，再让长链走到与短链等长的位置，之后两链同速走，若能相遇说明存在公共链

同样可以借助环思路的一道题：

61. Rotate List

(1) Rotate List - LeetCode

环思路解法：

 ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL) return NULL;
        //闭合成环+断开
        int n = 1;//记录链长
        ListNode* last = head;
        while(last->next){
            last = last->next;
            n++;
        }
        //与k比较确定处理步骤
        int round = k % n;
        if(round == 0)  return head;
        
        //连接成环
        last->next = head;
        //快慢指针找到倒数第round+1个进行断链
        ListNode* fast = head;
        ListNode* slow = head;
        //注意快慢指针的处理——前面已经闭合成环
        for(int i=0;i<=round;i++){
            fast = fast->next;
        }
       for(int j=0;j<n-round-1;j++){
            fast = fast->next;
            slow = slow->next;
        }//slow指向倒数第round+1个
        fast = slow->next;
        slow->next = NULL;
        return fast;
    }

先遍历链表获得相关信息

61. Rotate List

(1) Rotate List - LeetCode

解法一：闭合成环+断开

 ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL) return NULL;
        //闭合成环+断开
        int n = 1;//记录链长
        ListNode* last = head;
        while(last->next){
            last = last->next;
            n++;
        }
        //与k比较确定处理步骤
        int round = k % n;
        if(round == 0)  return head;
        
        //连接成环
        last->next = head;
        //快慢指针找到倒数第round+1个进行断链
        ListNode* fast = head;
        ListNode* slow = head;
        //注意快慢指针的处理——前面已经闭合成环
        for(int i=0;i<=round;i++){
            fast = fast->next;
        }
       for(int j=0;j<n-round-1;j++){
            fast = fast->next;
            slow = slow->next;
        }//slow指向倒数第round+1个
        fast = slow->next;
        slow->next = NULL;
        return fast;
    }

其实既然已经知道了表长，求倒数第k+1个结点就没有那么麻烦了，不需要快慢指针

ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL || k<0)   return head;
        //先遍历一次获取表长信息
        int n = 1;
        ListNode* last = head;
        while(last->next){
            last = last->next;
            n++;
        }
       //k与表长n进行比较确定处理方式
        
        int round = k % n;
        if(round==0)    return head;
        
        //已知表长，可直接找到倒数 第round+1个
        ListNode* p = head;
        for(int i = n-round-1;i>0;i--){
            p = p->next;
        }//找到倒数 第round+1个
        //直接断开
        ListNode* newHead = p->next;
        p->next = NULL;
        last->next = head;
        return newHead;
    }

摘结点建新链

21. Merge Two Sorted Lists

Merge Two Sorted Lists - LeetCode

设置哑结点不断摘到新链上

 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = (ListNode*)malloc(sizeof(ListNode));
        head->next = NULL;
        ListNode* r = head;
        while(list1 && list2){
            if(list1->val < list2->val){
                r->next = list1;
                list1 = list1->next;
            }
            else{
                r->next = list2;
                list2 = list2->next;
            }
            r = r->next;
        }
        while(list1){
           r->next = list1;
           list1 = list1->next;
           r = r->next;
        }    
        while(list2){
           r->next = list2;
           list2 = list2->next;
           r = r->next;
            
        }    
        r = head;
        head = head->next;
        free(r);
        return head;
    }

23. Merge k Sorted Lists

Merge k Sorted Lists - LeetCode

k个元素比较大小的思路：使用二叉堆-优先队列

关于优先队列的使用，参考：

ACM向：关于优先队列priority_queue自定义比较函数用法整理_一苇以航-CSDN博客_priority_queue 自定义比较

//priority_queue类默认为大根堆，需要修改比较器为小根堆

class Solution {
public:
    struct compare{//priority_queue类默认为大根堆，需要修改比较器为小根堆
        bool operator()(const ListNode* a,const ListNode* b){
        return a->val > b->val;
    }
};
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //实际运用：外排？
        //使用堆排序找到最小的结点作为第一个插入结点
        
        //建堆
        std::priority_queue<ListNode*,vector<ListNode*>,compare> pq;自定义一个比较类，为小根堆
        int n = lists.size();
        for(int i=0;i<n;i++){
            if(lists[i])    pq.push(lists[i]);
        }
        ListNode* head = new ListNode(0);//dumpy node
        head->next = NULL;
        ListNode* r = head;
        while(pq.size()){
            ListNode* cur = pq.top();
            pq.pop();
            r->next = cur;
            r = r->next;//尾插法加入新链中
            if(cur->next)   pq.push(cur->next);
        }
        return head->next;
    }
};

O（nlogn）time

另一思路：归并排序的思路，先两两合并

每一次，对于list所存链进行两两合并，合并后的新链存在一个newlist中

重复上述步骤——使用递归

两两合并处理数组的思路：

①从后→前合并：数组会在原数组上缩小，但存回去得用新数组存

②从前→后存：动态数组实际上涉及数组的移动

③前＋后两两取出再放回（前）的位置，然后删除（后）的旧记录

使用while：

 ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        int n = lists.size();
        if(n==0)    return NULL;
        if(n==1)    return lists[0];
        
        int rear = n-1;
        int front=0;
        //前后取元素完成一次合并-缩小规模
        while(front < rear){
            ListNode* newHead = mergeTwoLists(lists[front],lists[rear]);
            lists[front] = newHead;
            lists.pop_back();//把rear pop出来
            rear --;
            front ++;
        }
        //递归的完成下一轮
        return mergeKLists(lists);
    }

使用for：

 ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        //递归基
        if(n==0)    return NULL;
        if(n==1)    return lists[0];
        
        for(int i=0;i<n/2;i++){
            lists[i] = mergeTwoList(lists[i],lists[n-i-1]);
            lists.pop_back();
        }
        return mergeKLists(lists);
    }
    
    ListNode* mergeTwoList(ListNode* la,ListNode* lb){
        ListNode* head = new ListNode(0);
        head->next = NULL;
        ListNode* r = head;
        while(la && lb){
            if(la->val <= lb->val){
                r->next = la;
                la = la->next;
            }
            else{
                r->next = lb;
                lb = lb->next;
            }
             r = r->next;
        }
        while(la){
            r->next = la;
            la = la->next;
            r = r->next;
        }
        while(lb){
            r->next = lb;
            lb = lb->next;
            r = r->next;
        }
        return head->next;
    }

递归的逻辑是一颗倒立的二路归并树

 这里是使用了归并排序两两归并的思路，由于lists是链表头，并非有序数组，故可以使用前+后的for循环方式，原地归并

attention：实际上对于修改lists[i]，由于其底层实现是数组，存在额外的元素移动

Otime（nlogk）n：总结点数，k：总链数

206. Reverse Linked List

Reverse Linked List - LeetCode

解法一：头插法实现逆转

摘新链+添加dummy node统一化操作

ListNode* reverseList(ListNode* head) {
        if(head==NULL)  return NULL;
        ListNode* virtualhead = new ListNode(-1);
        virtualhead->next = head;
        ListNode* cur = head->next;
        head->next = NULL;
        while(cur){
            ListNode* p = cur->next;
            cur->next = virtualhead->next;
            virtualhead->next = cur;
            cur = p;
        }
        return virtualhead->next;
    }

解法二：多指针改变链的转向

 ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* cur = head;
        ListNode* post = NULL;
        while(cur){
            post = cur->next;
            cur->next = prev;//转向
            prev = cur;
            cur = post;
        }
        return prev;
    }

解法三：递归

由解法二考虑是否能用递归

输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点

 ListNode* reverseList(ListNode* head) {
        //递归基
        if(head==NULL || head->next == NULL)    return head;
        //对于头一个节点，让递归函数帮忙递归其后的结点
        ListNode* last = reverseList(head->next);//已翻转的链，返回链头
        //将本结点head链接到表尾
        head->next->next = head;
        head->next = NULL;
        return last;
    }

同类题/逆转的应用：

234. Palindrome Linked List

(1) Palindrome Linked List - LeetCode

思路：快慢指针找到中间结点后将后半结点逆转，再进行比较

 bool isPalindrome(ListNode* head) {
        
        //添加dummy使得逆转时处理从next开始
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next;
            if(fast)    fast = fast->next;  
        }//找到middle(slow指向元素),其指向中间（单数）|| 前一个（双数）
     
        slow->next = reverse(slow->next);
        fast = slow->next;
        slow = head;
        while(fast){//fast指向NULL则遍历完了
            if(slow->val!=fast->val)    return false;
            slow = slow->next;
            fast = fast->next;
        }
        return true;
    }
    //逆转以head为头结点的链表并返回链头
    ListNode* reverse(ListNode* head){
        ListNode* pre = NULL;
        ListNode* p = head;
        ListNode* post = NULL;
        while(p){
            post = p->next;
            p->next = pre;
            pre = p;
            p = post;
        }
        return pre;
    }

 缺点：改变了原始链表结构

改进：最后在翻转回来

92. Reverse Linked List II

Reverse Linked List II - LeetCode

同一递归思路：只是修改逆转的链头和链尾而已。其中，链尾需要使用全局变量进行记录

ListNode* last_next = NULL;
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(head==NULL) return NULL;
        int go = 1;
        ListNode* prev = head;
        while(prev && go<left-1){
            prev = prev->next;
            go++;
        }
        if(left==1)   return reverse(head,right-left+1);//special case的解决
        prev->next = reverse(prev->next,right-left+1);//special case:left==1,此时无前驱
        return head;
    }
    ListNode* reverse(ListNode* head,int n){
        
        if(n==1){
            last_next = head->next;
            return head;
        }
        if(head==NULL || head->next==NULL)  return NULL;
        ListNode* last = reverse(head->next,--n);
        head->next->next = head;
        head->next = last_next; //怎么把last的next传进来—使用一个全局变量
        return last;
    }

优化递归思路：

使用条件判断把整条链都置于递归处理中

ListNode* last_next = NULL;
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left==right){//递归基-到达最后一个待翻转元素
            last_next = head->next;
            return head;//单元素的逆转是其本身，直接返回
        } 
        if(left>1){//还未到达需要翻转的结点,找到翻转结点时left坐标应该为1
            head->next = reverseBetween(head->next,left-1,right-1);//以下一结点为起始结点，坐标-1
            return head;
        }
        else{//需要翻转结点:left<right&&left==1
            ListNode* last = reverseBetween(head->next,1,right-1);//left==1需要翻转
            head->next->next = head;//翻转本链
            head->next = last_next;
            return last; 
        }

left和right充当双指针

当前递归函数每走一步，right则-1，所以当递归（遍历）到最后一个待翻转函数时，right==1，

当递归到第一个待翻转函数时，left==1.

skill：第一个待翻转函数后，让left始终为1

递归的逻辑：

处理当前结点head，让递归函数帮忙处理head->next：

处理head

head->next = helper(head->next,递归所需的其他信息)//设置head->next

递归所需的其他信息：

可能为对应的边界条件

在本题中使用整数代表双指针遍历的情况

所以链表递归主要是一直往后遍历，让递归函数返回正确的head->next

非递归思路：

ListNode* reverseBetween(ListNode* head, int left, int right) {
        //头插法逆转+dummy统一化
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* prev = dummy;
        int n = right-left;
        while(left>1){
            prev = prev->next;
            left--;
        }//prev指向头插法的头结点
        ListNode* cur = prev->next;//待逆转的第一个结点
        ListNode* post = NULL;
        while(cur && n>0){
            post = cur->next;
            cur->next = cur->next->next;
            post->next = prev->next;
            prev->next = post;
            n--;
        }
        return dummy->next;
    }

25. Reverse Nodes in k-Group

Reverse Nodes in k-Group - LeetCode

为保持上一轮与下一轮指针相连，不宜使用三指针改变转向方式逆转，应该使用头插法逆转

使用一个fast先探路：

 ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* prev = dummy;
        ListNode* cur = prev->next;
        ListNode* post = NULL;
        ListNode* fast = dummy;
        while(true){
            //先设置一个快指针判断是否可逆转
             int n = k-1;
            while(n>=0 && fast){//fast正好指向可逆转的最后一个元素
                fast = fast->next;
                n--;
            }
            if(fast==NULL) break;//不可逆转
            n = 1;
            while(n<k){
                post = cur->next;
                cur->next = cur->next->next;
                post->next = prev->next;
                prev->next = post;
                n++;
            }
            prev = cur;//下一轮
            fast = cur;
            cur = prev->next;
        }
       return dummy->next;
    }

递归思路：

基于快指针的思路，快指针最后正好指向了本组可逆转的最后一个元素

转换思路为逆转链表结点a，b之间的元素 

实际上就是逆转a==head与b==NULL之间的元素

  ListNode* last = head;
        int n = k;
        while(n>0){
            if(last==NULL) return head;//不需要逆转
            last = last->next;
            n--;
    }//last指向了待逆转的最后一个元素的下一个元素——方便递归传递参数
        
        ListNode* prev = head;
        ListNode* cur = prev->next;
        ListNode* post = NULL;
        n = k;
        while(n>1){
            post = cur->next;
            cur->next = prev;
            prev = cur;
            cur = post;
            n--;
        }
        head->next = reverseKGroup(last,k);
        return prev;
    }

（四）添加dummy node统一化操作

19. Remove Nth Node From End of List

Remove Nth Node From End of List - LeetCode

 ListNode* removeNthFromEnd(ListNode* head, int n) {
        //双指针
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* virtualhead = new ListNode(0);//虚拟头结点——统一化special case:为头结点
        virtualhead->next = head;
        ListNode* pre = virtualhead;//删除结点需要保留其头结点
        //fast先走
        while(n--&&fast)     fast = fast->next;
        if(fast==NULL&& n>0) return NULL;//输入无效
        while(fast){
            fast = fast->next;
            pre = slow;
            slow = slow->next;
        }//slow指向了欲删除结点
        pre->next = slow->next;
        return virtualhead->next;
    }

变式：

24. Swap Nodes in Pairs

(1) Swap Nodes in Pairs - LeetCode

两两相邻交换正好是k=2的特殊情况

ListNode* swapPairs(ListNode* head) {
        //可以看成k个一组逆转
        return reverseKGroup(head,2);
    }
    ListNode* reverseKGroup(ListNode* head,int k){
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* fast = dummy;
        ListNode* preHead = dummy;
        ListNode* cur = head;
        ListNode* post = NULL;
        while(true){
            //fast指针先探路
            int count = 0;
            while(fast && count<k){
                count++;
                fast = fast->next;
            }
            if(fast==NULL) break;//不用逆转
            //fast指向了待逆转的最后一个结点
            count = 1;
            while(count<k){
                post = cur->next;
                cur->next = cur->next->next;
                post->next = preHead->next;
                preHead->next = post;
                count++;
            }
            preHead = cur;
            cur = preHead->next;
            fast = preHead;
        }
        return dummy->next;
    }

解法二：根据解法一，仍可考虑递归操作

仍是递归思路的思考——子问题

本结点只处理一个子问题，让递归函数帮忙处理余下的子问题

本题的子问题是交换一对：

本函数让递归函数帮忙处理余下子问题（余下所有链）并返回余下子链的头结点

本函数处理本组pair

本函数pair+余下子链pair==整个本链完成swap，返回给上一递归函数作为其next

-->链表递归是在正确处理head->next

 ListNode* swapPairs(ListNode* head) {
        //递归基
        if(head==NULL)  return NULL;
        if(head->next==NULL) return head;
        //本结点让递归函数帮忙swap余下组链并返回链头
        //本结点交换本组Pair
        //本结点所在组+余下组链完成swap——>以本结点组为链头的链完成swap,返回新链头给上一递归函数
        ListNode* post = head->next;
        head->next = swapPairs(post->next);
        post->next = head;
        return post;
    }

解法三：

为保持交换过程不断链，使用两个辅助指针pre和post

加入dummy统一化操作

 ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* pre = dummy;
        while(pre->next && pre->next->next){
            ListNode* a = pre->next;
            ListNode* b = a->next;
            ListNode* post = b->next;
            pre->next = b;
            b->next = a;
            a->next = post;
            pre = a;
        }
        return dummy->next;
    }

82. Remove Duplicates from Sorted List II

(1) Remove Duplicates from Sorted List II - LeetCode

理解为子链删除：

 ListNode* deleteDuplicates(ListNode* head) {
        if(head == NULL || head->next == NULL)  return head;
        
        //dummy统一化操作
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        //pre用于删除pre->next,first,last用于标记相等子链的首和尾的下一个
        ListNode* pre = dummy;
        ListNode* first = head;
        ListNode* last = first->next;
        while(last){
            
            while(last && first->val == last->val){
                last = last->next;
            }
            if(first->next==last){//不重复
                pre = first;
                first = last;
            }
            else{    //重复，需要删除
                first = last;
                pre->next = first;
            }
            if(first)   last = first->next;
        }
        return dummy->next;
    }

（五）链表长度不一致的处理

2. Add Two Numbers

(1) Add Two Numbers - LeetCode

两加数相加需逆序处理

相加可能需要进位

最高位可能由于进位需要创建新结点

 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(-1);
        head->next = NULL;
        ListNode* rear = head;
        //判断是否进位
        int flag = 0;
        while(l1 && l2){
            int sum = l1->val+l2->val+flag;
            ListNode* p = new ListNode(sum % 10);
            rear->next = p;
            rear = rear->next;
            if(sum>=10){ 
                flag = 1;
                if(l1->next==NULL && l2->next==NULL){
                    ListNode* p = new ListNode(1);
                    rear->next = p;
                    rear = rear->next;
                }
            }
            else 
                flag = 0;
            l1 = l1->next;
            l2 = l2->next;
        }
        while(l1){
            int sum = l1->val + flag;
            ListNode* p = new ListNode(sum % 10);
            rear->next = p;
            rear = rear->next;
            if(sum >= 10){ 
                flag = 1;
                if(l1->next==NULL){//l1指向最后一个元素且需要进位
                    ListNode* p = new ListNode(1);
                    rear->next = p;
                    rear = rear->next;
                }
            }
            else 
                flag = 0;
            
             l1 = l1->next;
        }
        
         while(l2){
            int sum = l2->val + flag;
            ListNode* p = new ListNode(sum % 10);
            rear->next = p;
            rear = rear->next;
            if(sum>=10){ 
                flag = 1;
                if(l2->next==NULL){//l1指向最后一个元素且需要进位
                    ListNode* p = new ListNode(1);
                    rear->next = p;
                    rear = rear->next;
                }
            }
            else 
                flag = 0;
              l2 = l2->next;
        }
        return head->next;
    }

借鉴计组加法器的实现原理：进位只是＋1，不进位则+0，可以直接使用一个标志位模拟每次进位的情况

总结：链表长度不一致的处理可以使用三循环

链表复制

138. Copy List with Random Pointer

(1) Copy List with Random Pointer - LeetCode

初始思路：

由于random指针指向任意一个结点，不能边遍历边完成新结点的建立。

所以考虑先建立好新结点再处理新结点的random指针

所以一开始建立新结点时其random指针无用，可以利用它存储信息——建立指向关系

让newnode的random存储对应oldnode的random，oldndoe的random用来存储oldnode对应的newnode

这样，处理newnode的random时，根据newnode的random找到oldnode的random，再由这个oldnode的random找到其对应的newnode，完成链接，同时基于newnode的random改回oldnode的random，保持原始链表的不变性

上述思路行不通，原因是random可能多次指向同一结点，第一次random指向a时正确，并修改回了原链表。第二个random指向a时由于第一个random时已经改回，故无法再成功指向

思路二：

新建立的新结点不要另外存放在一条新链上，而是间隔保持在原链上。这样指针之间的指向关系仍可保持。

奇数i(oldnode)的random为k，偶数i+1(newnode)的random为k+1

 Node* copyRandomList(Node* head) {
        if(head==NULL)  return NULL;
        Node* p = head;
        Node* post = NULL;
        //复制新结点到原链表上
        while(p){
            post = p->next;
            Node* newnode = new Node(p->val);
            newnode->next = post;
            p->next = newnode;
            p = post;
        }
        p = head;
        //在原链表上处理新链表的random
        while(p){
            post = p->next;
            if(p->random==NULL){
                post->random = NULL;
            }
            else{
                post->random = p->random->next;
            }
            p = post->next;
        }
        //摘下新结点
        Node* newHead = new Node(-1);
        newHead->next = NULL;
        Node* newTail = newHead;
        p = head;
        while(p){
            post = p->next;
            p->next = post->next;
            post->next = NULL;
            newTail->next = post;
            newTail = newTail->next;
            p = p->next;
        }
        
        return newHead->next;
    }