链表操作总结

单向链表的操作大致可以总结为插入，删除和反转。根据问题，可以将一般解法依照单向链表的特征进行改造。

• 1. 插入 插入需要保留一个指向插入点之前的一个元素的指针。插入后需要更改插入元素的next指针所指向的内容。需要注意如果插入元素来自另一个链表，需要在更改next之前将指向插入元素的指针先更新（cur = cur->next， cur = cur->next->next(移除)或者是其它操作)。不然会造成问题。

  错误的例子：

    ListNode* nxt = cur->next;
    cur->next = temp;
    cur->next->next = node;
    temp = temp->next;
  

  由于先更新了cur->next->next 会导致temp->next 也会一并更新为node。如果之后再访问temp->next, 则相当于访问cur->next， 这样就相当于把两个链表在此合并，原来temp之后的内容就访问不到了。

  正确的做法就应当先进行temp的更新再进行cur->next->next更新，这样就可以避免temp->next的内容被覆盖掉。

  典型的插入操作比如insertion sort

  // res->next = head;
  while (cur->next != null) {
      if (cur->next->val < cur->val) {
          while (temp->next->val < cur->next->val) temp = temp->next;
           ListNode* nxt = temp->next;
          temp->next = cur->next;
          cur->next = cur->next->next; // remove
          temp->next->next = nxt;
          temp = res;
      } else {
          cur = cur->next;
      }
  }
  

  思路是先从最前开始找插入点，最后插入该元素并重置链接。

  1. 合并链表

     其实就是插入操作的集合，跟数组插入的逻辑是差不多的。

     比如Merge sort里面的merge。

  ListNode res = ...
  while (left != null && right != null) {
      if (left->val > right->val) {
  		res->next = left;
          left = left->next;
          res->next->next = null;
          res = res->next;
      } else {
          insert left;
      }
  }
  // After insertion, set res->next to null;
  while (left != null) {
  	res->next = left;
      res = res->next;
      left = left->next;
  }
  while (right != null) {
      ...
  }
  

  1. 将链表分成两半

     一个快指针和一个慢指针同时跑。注意指针的初始设置会影响拆分结果。

     因为最后划分去的是慢指针的next，所以我们一般情况下应当让慢指针指向划分点的前一个元素，所以一般情况下将慢指针初始化为next为第一个元素的指针。长度为偶数的情况下是对半分，长度为奇数情况下多的一个元素会在右侧。

     划分之后要将slow->next设置为null。

  2. 反转一个链表

     记录prev, cur, nxt, 每次将cur的next指向pre, 然后更新prev, nxt, cur。

  3. 注意事项

     1.如果要访问cur->next->next，则先要保证cur->next不为null。

     2.插入的时候要看的是cur->next。

     3.链表长度为一的时候经常需要特判。

     4.链表指针为空的时候插入的特殊处理。