剑指Offer刷题笔记：链表

链表

链表常用解法

递归

考虑：终止条件、递归前逻辑处理、递归后逻辑处理

终止条件一般为传入节点为空时

若需要对链表从尾到头操作，则一般进行递归后逻辑处理。即先依次把节点压入操作栈，直到最后一个节点，再执行操作，依次出栈（如：倒序打印、反转链表）

善于假设。假设递归结果就是以处理完成的链表

双指针

通常分哨兵指针（用于保存链表），遍历指针（用于遍历链表，循环后移）

哨兵指针尽量为申请为ListNode(-1)，下一个节点连接原链表头结点。这样有利于删除节点

倒序操作链表

从尾到头打印链表（简单）

头插法

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    // 方法一：头插法
    // 利用ArrayList的方法，在指定0索引位插入元素
    ArrayList<Integer> list = new ArrayList<>();

    ListNode temp = listNode;
    while(temp != null){
        list.add(0,temp.val);
        temp = temp.next;
    }
    return list;
}

递归

ArrayList<Integer> list = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    // 方法二：递归
    // 终止条件
    if(listNode != null){
        // 先把操作压入栈，链表中最后一个节点进栈后才开始add
        printListFromTailToHead(listNode.next);
        // 递归后逻辑操作，add，即从尾到后add
        list.add(listNode.val);
    }
    return list;
}

反转链表（简单）

使用栈

public ListNode ReverseList(ListNode head) {
    // 方法一：使用栈
    // 遍历链表，依次将节点压入栈内，再依次从栈中取出，形成新链表

    // 0.生成栈
    Stack<ListNode> stack = new Stack<>();
    // 1.遍历，压栈
    while(head != null){
        stack.push(head);
        head = head.next;
    }
    // 判断是否空栈
    if(stack.isEmpty()){
        return null;
    }

    // 2.出栈
    ListNode node = stack.pop();
    ListNode res = node;// 增加一个指针，node指针后移，res指针记录结果头
    while(!stack.isEmpty()){
        ListNode tmpNode = stack.pop();
        node.next = tmpNode;
        node = node.next;
    }
    // 清除最后一个节点的next
    node.next = null;
    return res;
}

双链表（头插法）

public ListNode ReverseList(ListNode head) {
    // 方法二：双链表（头插法）
    ListNode newHead = null;
    while(head != null){
        // temp指针保存原链表
        ListNode temp = head.next;
        // 将head节点插入新链表的头部
        head.next = newHead;
        // 将新链表newHead指向被清空的head
        newHead = head;
        // head重新指向原链表
        head = temp;
    }
    return newHead;
}

合并两个排序的链表（简单）

递归（不太明白）

public ListNode Merge(ListNode list1, ListNode list2) {
    // 特殊情况判断（也是递归的终止条件）
    if (list1 == null)
        return list2;
    if (list2 == null)
        return list1;
    // 递归
    // 从头结点开始，值较小的list后面跟merge好的链表，每次返回都是排序好的链表头
    if(list1.val <= list2.val){
        list1.next = Merge(list1.next,list2);
        return list1;
    }else{
        list2.next = Merge(list2.next,list1);
        return list2;
    }
}

双指针

public ListNode Merge(ListNode list1, ListNode list2){
    // 方法1
    // 设置newHead记录新链表，依次向后移，设置res作为哨兵指针
    ListNode newHead = new ListNode(-1);
    ListNode res = newHead;
    while (true) {
        // 若都为空，则代表取完了
        if(list1 == null && list2 == null){
            break;
        }
        if(list1 == null){
            // list1取完，将list2全部连到新链表尾部
            newHead.next = list2;
            break;
        }else if(list2 == null){
            // list2取完，将list1全部连到新链表尾部
            newHead.next = list1;
            break;
        }else if(list1.val <= list2.val) {
            // list1较小，连上新链表尾部，继续遍历
            newHead.next = list1;
            newHead = newHead.next;
            list1 = list1.next;
        }else if(list1.val > list2.val){
            // list2较小，连上新链表尾部，继续遍历
            newHead.next = list2;
            newHead = newHead.next;
            list2 = list2.next;
        }
    }
    return res.next;
}

优化双指针

public ListNode Merge(ListNode list1, ListNode list2){
    // 方法2
    ListNode newHead = new ListNode(-1);
    ListNode res = newHead;
    while(list1 != null && list2 != null){
        if(list1.val <= list2.val){
            newHead.next = list1;
            newHead = newHead.next;
            list1 = list1.next;
        }else{
            newHead.next = list2;
            newHead = newHead.next;
            list2 = list2.next;
        }
    }
    if(list1 == null && list2 != null){
        newHead.next = list2;
    }
    if(list2 == null && list1 != null){
        newHead.next = list1;
    }
    return res.next;
}

寻找链表中环入口节点（中等）

快慢双指针

public ListNode EntryNodeOfLoop(ListNode pHead) {
    // 方法1：快慢双指针
    // 若有环，快慢指针必相遇。设快慢指针相遇点p，环入口q，从头结点到q距离A，qp两点距离B，pq两点距离C
    // 则有：2(A+B)=A+B+C+B --> A = C
    // 即，从起点到环入口距离 = 相遇点回到环入口距离(pq距离)
    // 相遇后，启动慢指针2号，从起点出发，与慢指针相遇时，二者都恰好走到环入口
    // 时间复杂度O(n)：n是链表长度、空间复杂度O(1)：只使用了三个指针
    if(pHead == null || pHead.next == null){
        return null;
    }
    // 设置快慢双指针
    ListNode fast = pHead;
    ListNode slow = pHead;
    // 快指针走2步，慢指针走1步
    while(fast != null && fast.next.next != null){
        fast = fast.next.next;
        slow = slow.next;
        // 相遇
        if(fast == slow){
            // 启动慢指针2号
            ListNode slow2 = pHead;
            while(slow != slow2){
                slow2 = slow2.next;
                slow = slow.next;
            }
            // 相遇点即为环入口点
            return slow2;
        }
    }
    return null;
}

集合

public ListNode EntryNodeOfLoop(ListNode pHead){
  // 方法2：集合
  // 将节点一个个全部存放到集合中，若出现重复节点，则说明有环，且首次重复的节点就是环入口
  // 时间复杂度O(n)：n为链表长度、空间复杂度O(n)：所有节点存放入集合中
  Set<ListNode> set = new HashSet<>();    while(pHead != null){
    // 若有重复节点，则说明有环，返回此重复节点
    if(!set.add(pHead)){
      return pHead;
    }
    // 若无重复节点，继续遍历，直到末尾
    pHead = pHead.next;
  }
  return null;
}

深拷贝复杂链表（较难）

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;
    RandomListNode(int label) {
        this.label = label;
    }
}*/
import java.util.*;
public class Solution {
  public RandomListNode Clone(RandomListNode head) {
    // 双指针，一个遍历原链表，另一个构造新链表
    // 同时用保存原链表节点与新链表节点的映射关系，便于拷贝random关系
    // 再同时对新链表和原链表进行遍历，通过哈希表的映射，为新链表构建random关系
    Map<RandomListNode,RandomListNode> map = new HashMap<>();
    // 新链表的头指针，用于返回结果
    RandomListNode newHead = new RandomListNode(-1);
    // 新链表的尾指针
    RandomListNode tail = newHead;
    // temp指针用于遍历原链表
    RandomListNode temp = head;
    // 遍历原链表
    while(temp != null){
      RandomListNode node = new RandomListNode(temp.label);
      map.put(temp,node);
      //保存新链表与原链表的映射关系，便于构建random关系
      tail.next = node;//新节点连入新链表尾部
      tail = tail.next;//尾指针移动
      temp = temp.next;//temp指针移动
    }
    tail = newHead.next;
    //新链表尾指针回到头部，进行下一次遍历
    RandomListNode temp2 = head;
    //temp2指针用于第二次遍历原链表
    while(temp2 != null){
      if(temp2.random != null){
        //从哈希表中取出random关系
        tail.random = map.get(temp2.random);
      }
      tail = tail.next;
      temp2 = temp2.next;
    }
    return newHead.next;
  }
}

删除

删除链表的节点（简单）

双指针（自己写）

public ListNode deleteNode (ListNode head, int val) {
  // write code here
  // 双指针，设立哨兵指针res，保存头结点（自己写的，比较复杂）
  // next指针遍历链表，对比val，若相同，则删除节点
  if(head == null){
    return null;
  }
  if(head.next == null){
    if(head.val == val){
      return null;
    }
    return head;
  }
  ListNode res = head;
  while(head != null){
    ListNode next = head.next;
    if(head.val == val){
      return next;
    }else if(next.val == val){
      // 删除此节点
      head.next = next.next;
      return res;
    }
    head = head.next;
  }
  return res;
}

双指针（参考别人，简洁版）

public ListNode deleteNode (ListNode head, int val){
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  ListNode temp = dummy;
  while(temp.next != null){
    if(temp.next.val == val){
      temp.next = temp.next.next;
      break;
    }
    temp = temp.next;
  }
  return dummy.next;
}

删除链表中重复的节点（较难）

双指针迭代

public ListNode deleteDuplication(ListNode pHead) {
  // 方法1：迭代
  // 双指针，dummy指针代表虚拟头结点，保存结果链表头，tail指针后移，遍历链表
  // 判断节点“保留”or“跳过”：tail所指节点与下一个节点是否相同
  // 若下一节点为空，或节点不同，则保留，继续遍历
  // 若下一节点相同，则跳过此节点，直至下一个节点不同或为空
  // 代码如下：
  ListNode dummy = new ListNode(-1);
  ListNode tail = dummy;
  while(pHead != null){
    // 下一节点为空或不同，选择保留节点，连入tail末尾
    if(pHead.next == null || pHead.val != pHead.next.val){
      tail.next = pHead;
      tail = pHead;
    }
    // 下一节点相同，选择跳过节点
    while(pHead.next != null && pHead.val == pHead.next.val){
      pHead = pHead.next;
    }
    // 继续遍历
    pHead = pHead.next;
  }
  // 当最后节点重复时，pHead跳过，但tail未跳过，确保tail的末尾为空
  tail.next = null;
  return dummy.next;
}

递归

public ListNode deleteDuplication(ListNode pHead) {
  // 方法2：递归
  // 终止条件：节点为空或下一个节点为空时，直接返回pHead当前节点
  // 逻辑处理：递归前，判断当前节点与下一个节点是否相同，若不同则保留，相同则跳过
  if(pHead == null || pHead.next == null){
    return pHead;
  }
  if(pHead.val != pHead.next.val){
    //此节点保留，因此对下一个节点进行递归
    pHead.next = deleteDuplication(pHead.next);
    return pHead;//保留当前节点
  }else{//此节点需跳过，直到下一个为空或不同 
    ListNode temp = pHead;//使用temp指针遍历此重复节点链表
    while(temp != null && temp.val == pHead.val){
      temp = temp.next;
    }
    return deleteDuplication(temp);//对跳过后的节点进行递归，并返回
  }
}