小技巧

由于在进行链表操作时，尤其是删除节点时，经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题：

  • 一是尽量处理当前节点的下一个节点而非当前节点本身
  • 二是建立一个虚拟节点，使其指向当前链表的头节点，这样即使原链表所有的节点全部删除，也会有一个虚拟节点存在，返回 dummy->next即可。

  • 从前往后操作必须要dummy节点！！！！！

    链表的基本操作

    206. 反转链表

    迭代

  • 关键在于一个pre指针，以及一个next指针

    1. class Solution {
    2. public:
    3.   ListNode* reverseList(ListNode* head) {
    4.       ListNode* prev = nullptr,*next;
    5.       while(head != nullptr){
    6.           next = head -> next;
    7.           head -> next = prev;
    8.           prev = head;//prev表示前一个节点
    9.           head = next;//将头节点进行更新
    10.       }
    11.       return prev;
    12.   }
    13. };

    递归（从后往前）

  • 在递归中，当前节点是操作不了前面的节点的，所以cur->next = pre是不可能的，

  • 只能使用cur->next->next= cur，让后面的节点指向当前的节点。

  • 这里从后往前，先进入后面，然后再回归的时候进行操作。

    1. class Solution {
    2. public:
    3.   ListNode* reverseList(ListNode* head) {
    4.       if (!head || !head->next) {//如果head为空或者，head->next为空返回。
    5.           return head;
    6.       }
    7.       ListNode* newHead = reverseList(head->next);
    8.       head->next->next = head;
    9.       head->next = nullptr;
    10.       return newHead;
    11.   }
    12. };

    递归（从前往后）

    和迭代一样，从前往后操作，先操作然后进入。需要一个dummy节点。来实现先存储cur->next,然后cur->next = pre，

  • //只要找到最后一个节点全部都返回。把最后一个节点返回。

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head, ListNode* dummy = nullptr) {
  4.         if(!head) {
  5.             return dummy;
  6.         }
  7.         ListNode* node = head->next;
  8.         head->next = dummy;
  9.         return reverseList(node, head);//只要找到最后一个节点全部都返回。把最后一个节点返回。
  10.     }
  11. };

237. 删除链表中的节点（神思维）

image.png
因为链表不知道前面的一个节点是无法完成中间节点的删除的。这里有一个神思维，直接把要删除的节点变成下一个节点，然后把原本不需要删除的下一个节点删除掉。

  1. class Solution {
  2. public:
  3.     void deleteNode(ListNode* node) {
  4.         node->val=node->next->val;
  5.         node->next=node->next->next;   
  6.         return ;
  7.     }
  8. };

引发思考

这里为什么不用下面的代码来删除节点呢？

  1. class Solution {
  2. public:
  3.     void deleteNode(ListNode* node) {
  4.         node = node->next;
  5.     }
  6. };

因为这里的node本质上你可以看作是一个装地址的容器，你改变它的值本质上只是改变了这个容器的值，并没有改变原本链表的结构，只能通过node->next来进入到一个节点里面来改变结构。

83. 删除排序链表中的重复元素

  • 需要一个dummy来记住头节点

  • 注意delete养成好习惯，回收堆空间，防止内存泄漏。

    1. class Solution {
    2. public:
    3.   ListNode* deleteDuplicates(ListNode* head) {
    4.       ListNode *dummy = head;
    5.       while(dummy&&dummy->next){
    6.           if(dummy->val==dummy->next->val) {
    7.               ListNode *next = dummy->next;
    8.               dummy->next = next->next;
    9.               delete(next);
    10.           } else {
    11.               dummy = dummy->next;
    12.           }
    13.       }
    14.       return head;
    15.   }
    16. };

    21. 合并两个有序链表（使用dummy）

    迭代

  • 朴实无华的思路，和归并排序里面的排序有点像

    1. class Solution {
    2. public:
    3. ListNode* l3;
    4.   ListNode* mergeTwoLists(ListNode *l1, ListNode *l2) {
    5.       ListNode *dummy = new ListNode(0), *node = dummy;//这里就用到了那个思想，需要一个前置节点dummy
    6.       while (l1 && l2) {
    7.           if (l1->val <= l2->val) {
    8.               node->next = l1;
    9.               l1 = l1->next;
    10.           } else {
    11.               node->next = l2;
    12.               l2 = l2->next;
    13.           }
    14.           node = node->next;
    15.       }
    16.       node->next = l1? l1: l2;
    17.       return dummy->next;
    18.   }
    19. };

    递归

  • 思路想岔了，不应该新建一个节点

  • 因为新建的节点很难传递到递归的下一层。

ListNode* head1 = new ListNode();//如果没有后面的就是申请了一个空指针

  1. class Solution {
  2. public:
  3.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  4.         if (l1 == nullptr) {
  5.             return l2;
  6.         } else if (l2 == nullptr) {
  7.             return l1;
  8.         } else if (l1->val < l2->val) {
  9.             l1->next = mergeTwoLists(l1->next, l2);
  10.             return l1;
  11.         } else {
  12.             l2->next = mergeTwoLists(l1, l2->next);
  13.             return l2;
  14.         }
  15.     }
  16. };
  1. class Solution {
  2. public:
  3.     ListNode* head1();
  4.     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
  5.         dfs(list1, list2, head1);
  6.         return head1->next;
  7.     }
  8.     void dfs(ListNode* list1, ListNode* list2, ListNode* head){
  9.         if(!list1){
  10.             head->next = list2;
  11.             return ;
  12.         } 
  13.         if(!list2){
  14.             head->next = list1;
  15.             return ;
  16.         }
  17.         if(list1->val<list2->val){
  18.             head->next = list1;
  19.             dfs(list1->next, list2, head->next);
  20.         } else {
  21.             head->next = list2;
  22.             dfs(list1, list2->next, head->next);
  23.         }
  24.     }
  25. };

24. 两两交换链表中的节点（记得画图，常看）

迭代写法

  • 需要一个dummy

  • 画图就会清晰很多

    1. class Solution {
    2. public:
    3.   ListNode* swapPairs(ListNode* head) {
    4.       ListNode* dummyHead = new ListNode(0);
    5.       dummyHead->next = head;
    6.       ListNode* temp = dummyHead;
    7.       while (temp->next != nullptr && temp->next->next != nullptr) {
    8.           ListNode* node1 = temp->next;
    9.           ListNode* node2 = temp->next->next;
    10.           temp->next = node2;
    11.           node1->next = node2->next;
    12.           node2->next = node1;
    13.           temp = node1;
    14.       }
    15.       return dummyHead->next;
    16.   }
    17. };

    递归

    1. class Solution {
    2. public:
    3.   ListNode* swapPairs(ListNode* head) {
    4.       if (head == nullptr || head->next == nullptr) {
    5.           return head;
    6.       }
    7.       ListNode* newHead = head->next;
    8.       head->next = swapPairs(newHead->next);
    9.       newHead->next = head;
    10.       return newHead;
    11.   }
    12. };

    其他链表操作

    160. 相交链表（两个指针）

    从自己的头开始效率会低，从对方的头开始效率会高

    1. class Solution {
    2. public:
    3.   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    4.       ListNode *l1 = headA,*l2 = headB;
    5.       while(l1!=l2){
    6.           l1 = l1?l1->next:headB;
    7.           l2 = l2?l2->next:headA;
    8.       }
    9.       return l1;
    10.   }
    11. };

    234. 回文链表（链表中点+反转链表）

  • 先得到链表的中点，然后将后半部分反转

  • 同时遍历，看是否一样

    1. class Solution {
    2. public:
    3.   bool isPalindrome(ListNode* head) {
    4.       int num = 0;
    5.       ListNode *mid = head;
    6.       while(mid){
    7.           mid = mid->next;
    8.           num++;
    9.       }//得到最大长度
    10.       num = num%2==0? num/2:num/2+1;//取中位数
    11.       mid = head;
    12.       for(int i = 0; i < num; i++){
    13.           mid = mid->next;
    14.       }
    15.       mid = reverse(mid);//在中间反转链表
    16.       while(head&&mid){
    17.           if(head->val!=mid->val)//从中间开始遍历，不同则为false
    18.           return false;
    19.           head = head->next;
    20.           mid = mid->next;
    21.       }
    22.       return true;
    23.   }
    24.   ListNode* reverse(ListNode * head){//反转链表
    25.       ListNode* pre = nullptr;
    26.       ListNode* next;
    27.       while(head){
    28.           next = head->next;
    29.           head->next = pre;
    30.           pre = head;
    31.           head = next;
    32.       }
    33.       return pre;
    34.   }
    35. };

    328. 奇偶链表

  • 对于原始链表，每个节点都是奇数节点或偶数节点。头节点是奇数节点，头节点的后一个节点是偶数节点，相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。

  • even1指的是偶链表的尾节点，odd指的是奇数链表的偶节点。

    1. class Solution {
    2. public:
    3.   ListNode* oddEvenList(ListNode* head) {
    4.       if(!head) return head;
    5.       ListNode* odd = head, * even = head->next;
    6.       ListNode* even1 = even;
    7.       while(even1&&even1->next){
    8.           odd->next = even1->next;
    9.           odd = odd->next;
    10.           even1->next = odd->next;
    11.           even1 = even1->next;
    12.       }
    13.       odd->next = even;
    14.       return head;
    15.   }
    16. };

    19. 删除链表的倒数第 N 个结点(快慢指针)

  • 使用一个快指针先走到n的地方

  • 然后使用一个慢指针从头开始，这样的话，当快指针到达链表尾部的时候，慢指针就到了倒数第n个地方，因为快指针和慢指针之间差n个。

  • 注意删除的是头节点的情况

    class Solution {
public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
      ListNode* dummy = new ListNode(0), *pre;//使用一个dummy来判断链表是头节点的情况。
      ListNode* fast = dummy, *low = dummy;
      dummy->next = head;
      int num = 0;
      while(num<n){
          num++;
          fast = fast->next;
      }
      while(fast){
          fast=fast->next;
          pre = low;
          low = low->next;
      }
      pre->next = low->next;
      pre = dummy->next;
      delete(dummy);//注意防止内存泄漏的情况
      return pre;
  }
};

    148. 排序链表（归并排序）

    归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是 )O(logn)。如果要达到 O(1) 的空间复杂度，则需要使用自底向上的实现方式。

    自顶向下

    对链表自顶向下归并排序的过程如下。

  • 找到链表的中点，以中点为分界，将链 表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 11步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

  • 对两个子链表分别排序。

  • 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。

    class Solution {
public:
  ListNode* sortList(ListNode* head) {
      return sortList(head, nullptr);
  }

  ListNode* sortList(ListNode* head, ListNode* tail) {
      if (head == nullptr) {
          return head;
      }
      if (head->next == tail) {
          head->next = nullptr;//为每个小子集加上nullptr结尾
          return head;
      }
      ListNode* slow = head, *fast = head;
      while (fast != tail) {
          slow = slow->next;
          fast = fast->next;
          if (fast != tail) {
              fast = fast->next;
          }
      }
      ListNode* mid = slow;
      return merge(sortList(head, mid), sortList(mid, tail));
  }

  ListNode* merge(ListNode* head1, ListNode* head2) {
      ListNode* dummyHead = new ListNode(0);
      ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
      while (temp1 != nullptr && temp2 != nullptr) {
          if (temp1->val <= temp2->val) {
              temp->next = temp1;
              temp1 = temp1->next;
          } else {
              temp->next = temp2;
              temp2 = temp2->next;
          }
          temp = temp->next;
      }
      if (temp1 != nullptr) {
          temp->next = temp1;
      } else if (temp2 != nullptr) {
          temp->next = temp2;
      }
      return dummyHead->next;
  }
};

    自底向上

  • 用 subLength 表示每次需要排序的子链表的长度，初始subLength=1。

  • 每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2）。合并两个子链表仍然使用「21. 合并两个有序链表」的做法。

  • 将subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。

    class Solution {
public:
  ListNode* sortList(ListNode* head) {
      if (head == nullptr) {
          return head;
      }
      int length = 0;
      ListNode* node = head;
      while (node != nullptr) {
          length++;
          node = node->next;
      }
      ListNode* dummyHead = new ListNode(0, head);
      for (int subLength = 1; subLength < length; subLength <<= 1) {
          ListNode* prev = dummyHead, *curr = dummyHead->next;
          while (curr != nullptr) {
              ListNode* head1 = curr;
              for (int i = 1; i < subLength && curr->next != nullptr; i++) {
                  curr = curr->next;
              }
              ListNode* head2 = curr->next;
              curr->next = nullptr;
              curr = head2;
              for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {
                  curr = curr->next;
              }
              ListNode* next = nullptr;
              if (curr != nullptr) {
                  next = curr->next;
                  curr->next = nullptr;
              }
              ListNode* merged = merge(head1, head2);
              prev->next = merged;
              while (prev->next != nullptr) {
                  prev = prev->next;
              }
              curr = next;
          }
      }
      return dummyHead->next;
  }

  ListNode* merge(ListNode* head1, ListNode* head2) {
      ListNode* dummyHead = new ListNode(0);
      ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
      while (temp1 != nullptr && temp2 != nullptr) {
          if (temp1->val <= temp2->val) {
              temp->next = temp1;
              temp1 = temp1->next;
          } else {
              temp->next = temp2;
              temp2 = temp2->next;
          }
          temp = temp->next;
      }
      if (temp1 != nullptr) {
          temp->next = temp1;
      } else if (temp2 != nullptr) {
          temp->next = temp2;
      }
      return dummyHead->next;
  }
};

    147. 对链表进行插入排序

  • 首先判断给定的链表是不是只有一个

  • 创建哑节点dummy，为了方便在头部插入，令dummy->next=head。
  • 维护last代表链表已经完成排序的最后一个节点，初始时last=head；
  • 维护cur代表last节点的后一个节点，就是即将判断的节点，cur=head->next;
  • 比较last节点与cur节点的值
    • 如果last节点的值小于cur节点的值，就代表不需要进行别的操作。
    • 如果last节点的值大于cur节点的的值，就需要从链表头部dummy开始比较下一个节点的值和cur节点的值的大戏小。prev的下一个节点是第一个比cur大的节点，prev初始为dummy，为什么这里是prev的下一个节点呢，是为了方便后续的cur节点的插入。因为链表难以知道前一个节点的指针。
      class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
   if(!head->next) return head;
   ListNode* last = head, *dummy = new ListNode(0);
   dummy->next = head;
   ListNode* cur = head->next;
   while(cur) {
       if(last->val <= cur->val) {
           last = last->next;
       } else {
           ListNode* first = dummy;
           while(first->next->val <= cur->val) {
               first = first->next;
           }
           last->next = cur->next;
           cur->next = first->next;
           first->next = cur;
       }
       cur = last->next;
   }
   last = dummy->next;
   delete(dummy);
   return last;
}
};