合并有序链表

  1. // 21
  2. public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  3.         // 3. 递归跳出条件
  4.         if(list1 == null){
  5.             return list2;
  6.         }
  7.         if(list2 == null){
  8.             return list1;
  9.         }
  11.         // 1. 比较大小，值小的放入res 
  12.         ListNode res  = list1.val < list2.val?list1:list2;
  14.         // 2. 进行递归，res的下一个与list1、list2值较大的进行比较
  15.         // list1、list2来回切换逐一比较各自的值
  16.         res.next = mergeTwoLists2(res.next,list1.val >= list2.val?list1:list2);
  18.         return res;
  19.     }

删除链表中重复的元素

思路：记录上一个节点的元素，用来后续的比较，如果不相等，当前节点成为上一个节点
已经排过序的，逐一扫描,没有排序的可以借助存储（重点在重复上），如map、set等

  1. // 83
  2. public ListNode deleteDuplicates(ListNode head) {
  3.         if(head == null){
  4.             return null;
  5.         }
  7.         ListNode pre = head;
  8.         ListNode cur = head.next;
  10.         while(cur != null){
  11.             if(cur.val == pre.val){
  12.                 pre.next = cur.next;
  13.             }else{
  14.                 pre = cur;
  15.             }
  16.             cur = cur.next;
  17.         }
  18.         return head;
  19.     }
  21. // 203
  22. public ListNode removeElements(ListNode head, int val) {
  23.         ListNode res = head;
  24.         ListNode pre = head;
  25.         while(head != null){
  26.             if(head.val == val){
  27.                 pre.next = head.next;
  28.             }else{
  29.                 pre = head;
  30.             }
  31.             head = head.next;
  32.         }
  33.         if(res != null && res.val == val){
  34.             res = res.next;
  35.         }
  36.         return res;
  37.     }
  39. // 面试题 02.01. 移除重复节点
  40. public ListNode removeDuplicateNodes(ListNode head) {
  41.         Map map = new HashMap();
  42.         ListNode pre = head;
  43.         ListNode cur = head;
  44.         while(cur != null){
  45.             if(!map.containsKey(cur.val)){
  46.                 map.put(cur.val,cur);
  47.                 pre = cur;
  48.             }else{
  49.                 pre.next = cur.next;
  50.             }
  51.             cur = cur.next;
  52.         }
  54.         return head;
  55.     }

删除链表中的节点

思路：链表中的节点和值是两回事

  1. // 237. 删除链表中的节点
  2. // 将儿子的值给了它，然后它的孙子变成它的儿子
  3. public void deleteNode(ListNode node) {
  4.         node.val = node.next.val;
  5.         node.next = node.next.next;
  6.     }

链表的中间节点（快慢指针）

思路：快慢指针，快指针走完的时候，慢指针正好走到中间

  1. // 876. 链表的中间结点
  2. public ListNode middleNode(ListNode head) {
  3.         ListNode slow  = head;
  4.         ListNode fast  = head;
  5.         int k = 0;
  7.         while(fast != null && fast.next != null){
  8.             slow = slow.next;
  9.             fast = fast.next.next;
  10.             k++;
  11.         }
  12.         return slow;
  13.     }

查找倒数第k个结点

思路：
带头结点的单链表，结点结构为（data，next），在不改变链表的前提下，设计一个尽可能高效的算法，查找出链表中倒数第k（k为正整数）个位置上的结点。

第一种方法是先循环一遍链表确定结点个数n，则倒数第k个结点就是就是正数的第n+1-k个，然后在遍历一次链表就可以找到指定结点了，但显然需要遍历两遍链表。

第二种方法可以使用两个指针，第一个指针先走k-1步，然后第二个指针开始走。当第一个指针移动到最后时，第二个指针正好指向倒数第k个结点，只需要遍历一遍链表，显然更高效。