1.面试时链表解题的方法论

1)对于笔试，不用太在乎空间复杂度，一切为了时间复杂度

2)对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

2.链表面试题常用数据结构和技巧

1）使用容器(哈希表、数组等)

2）快慢指针

例如下面的功能：

1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点

2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点

3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个

4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

这种题目没有什么难度，只是抠边界（考察coding能力的）

3.力扣234回文链表

https://leetcode.cn/problems/palindrome-linked-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head.next == null) {
            return true;
        }
        int len = listLen(head);
        int i = 0;
        ListNode pre = null , cur = head, next = null;
        while (i < len / 2) {
            i++;
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // pre = 2 cur = 2   len偶数
        // pre = 2 cur = 3
        if (len % 2 == 1) {
            cur = cur.next;
        }
        while (pre != null) {
            if (pre.val != cur.val) {
                return false;
            }
            pre = pre.next;
            cur = cur.next;
        }
        return true;

    }

    public int listLen(ListNode h) {
        int ans = 0;
        while (h != null) {
            ans++;
            h = h.next;

        }
        return ans;
    }
}

4.牛客-链表分隔为3个区域

测试链接：（ACM风格）https://www.nowcoder.com/practice/04fcabc5d76e428c8100dbd855761778

将单向链表按某值划分为左边小，中间相等，右边大的形式

非常类似的题还有力扣86题：https://leetcode.cn/problems/partition-list/description/

题目描述：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

1）把链表放入数组里，在数组上做partition（笔试用）

2）分成小、中、大三部分，再把各个部分之间串起来（面试用）

下面只展示第二种解法：

import java.util.Scanner; 
import java.io.*;

class ListNode {
    int val;
    ListNode next;
    public ListNode(int x) {
        val = x;
        next = null;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int)in.nval;
            in.nextToken();
            int v = (int)in.nval;
            in.nextToken();
            ListNode head = new ListNode((int)in.nval);
            in.nextToken();
            ListNode cur = head;
            for (int i = 1;i < n;i++) {
                cur.next = new ListNode((int)in.nval);
                in.nextToken();
                cur = cur.next;
            }
            ListNode ans = partition(head, v);
            while (ans != null) {
                out.print(ans.val + " ");
                ans = ans.next;
            }
        }
        out.flush();
        br.close();
        out.close();
    }

    public static ListNode partition(ListNode head, int x) {
        if(head.next == null) {
            return head;
        }
        ListNode smallHead = null, equalHead = null, biggerHead = null;
        ListNode smallCur = null, equalCur = null, biggerCur = null;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                if (smallHead == null) {
                    smallHead = cur;
                    smallCur = smallHead;
                } else {
                    smallCur.next = cur;
                    smallCur = smallCur.next;
                }
            } else if (cur.val == x) {
                if (equalHead == null) {
                    equalHead = cur;
                    equalCur = equalHead;
                } else {
                    equalCur.next = cur;
                    equalCur = equalCur.next;
                }
            } else {
                if (biggerHead == null) {
                    biggerHead = cur;
                    biggerCur = biggerHead;
                } else {
                    biggerCur.next = cur;
                    biggerCur = biggerCur.next;
                }
            }
            cur = cur.next;
        }
        if (smallHead == null) {
            if (equalHead == null) {
                return biggerHead;
            } else {
                equalCur.next = biggerHead;
                if (biggerCur != null)biggerCur.next = null;
                return equalHead;
            }
        } else {
            if (equalHead == null) {
                smallCur.next = biggerHead;
                if (biggerCur != null) biggerCur.next = null;
            } else {
                smallCur.next = equalHead;
                equalCur.next = biggerHead;
                if (biggerCur != null) biggerCur.next = null;
            }
            return smallHead;
        }
    }
}

力扣86题解法参考：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        ListNode smallHead = null, biggerHead = null;
        ListNode smallCur = null, biggerCur = null;
        while (head != null) {
            if (head.val < x) {
                if (smallHead == null) {
                    smallHead = head;
                    smallCur = head;
                } else {
                    smallCur.next = head;
                    smallCur = smallCur.next;
                }
            } else {
                if (biggerHead == null) {
                    biggerHead = head;
                    biggerCur = head;
                } else {
                    biggerCur.next = head;
                    biggerCur = biggerCur.next;
                }
            }
            head = head.next;
        }
        // 至少2个节点
        if (smallHead == null) {
            return biggerHead;
        } else {
            if (biggerHead == null) {
                return smallHead;
            } else {
                smallCur.next = biggerHead;
                biggerCur.next = null;
                return smallHead;
            }
        }
    }
}

5.力扣138-随机链表的复制

测试链接：138. 随机链表的复制

一种特殊的单链表节点类描述如下

class Node { 
  int value; 
  Node next; 
  Node rand; 
  Node(int val) { value = val; } 
} 

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。【要求】时间复杂度O(N)，额外空间复杂度O(1)

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

\[0 <= n <= 1000\] \[-10^4 <= Node.val <= 10^4\]

Node.random 为 null 或指向链表中的节点。

解法1:容器

准备一个Map,key是老节点，value是新节点(这是第一次遍历)。然后第二次遍历，利用哈希表中的映射关系来设置新链表的 next 和 rand 指针。

对于每个老节点 cur：

新节点的 next 指针：map.get(cur).next = map.get(cur.next)。

新节点的 rand 指针：map.get(cur).rand = map.get(cur.rand)。

注意，如果 cur.next 或 cur.rand 为 null，map.get(null) 也会返回 null，这正是我们想要的。

返回头节点：最后返回新链表的头节点，即 map.get(head)。

class Solution {
    public Node copyRandomList(Node head) {
        // 0 <= n <= 1000
        if (head == null) return null;
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            Node newNode = new Node(cur.val);
            map.put(cur, newNode);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

解法2:不用容器

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;
        Node next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node copy = null;
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            copy.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }
        // 分离
        cur = head;
        Node res = cur.next;
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            cur.next = next;
            copy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }
}

6.力扣160-相交链表

160. 相交链表

给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null 【要求】如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }
}

如果要找到第一个相交的节点呢？(容器法:用HashMap就可以，不说了)

同时遍历两个链表到尾部，同时记录两个链表的长度。若两个链表最后的一个节点相同，则两个链表相交。有两个链表的长度后，我们就可以知道哪个链表长，设较长的链表长度为len1,短的链表长度为len2。则先让较长的链表向后移动(len1-len2)个长度。然后开始从当前位置同时遍历两个链表，当遍历到的链表的节点相同时，则这个节点就是第一个相交的节点。

测试链接：面试题 02.07. 链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/

牛客上也有类似题：https://www.nowcoder.com/practice/bd911c77a1ed4e289a0699fa7df23b6c

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46

https://www.nowcoder.com/questionTerminal/bd911c77a1ed4e289a0699fa7df23b6c?orderByHotValue=1&page=1&onlyReference=false

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode l1 = headA, l2 = headB;
        int m = 0, n = 0;
        while (l1.next != null) {
            m++;
            l1 = l1.next;
        }
        m++;
        while (l2.next != null) {
            n++;
            l2 = l2.next;
        }
        n++;
        // 判断是否相交
        if (l1 != l2) return null;
        // 否则相交
        int i = 0;
        ListNode l = m >= n ? headA : headB;
        ListNode s = headA == l ? headB : headA;
        while (i < Math.abs(n - m)) {
            i++;
            l = l.next;
        }
        // 
        while (l != s) {
            l = l.next;
            s = s.next;
        }
        return l;
    }
}

注意：

一个链表有环一个链表无环，则两者不可能相交
两个链表都有环时，考虑下面3种情况：
- 不相交
- 相交，且在同一个地方相交
- 相交，但不在同一个地方相交

如下图所示3种情况

两个链表的入环结点（loop1，loop2）如果是同一个，可以记录两个链表的差值，然后让长链表先走差值步以后，长短链表同时开始走，相遇的结点就是第一个相交结点。这是3种情况中最简单的。

剩下2 种情况如何判断？让loop1往下走，如果loop1走回到自己都没遇到loop2则属于上面情况1，如果loop1走回到自己之前遇到了loop2则属于情况3

public static Node getIntersectNode(Node head1, Node head2) {
  if (head1 == null || head2 == null) {
    return null;
  }
  Node loop1 = getLoopNode(head1);
  Node loop2 = getLoopNode(head2);
  if (loop1 == null && loop2 == null) {
    return noLoop(head1, head2);
  }
  if (loop1 != null && loop2 != null) {
    return bothLoop(head1, loop1, head2, loop2);
  }
  return null;
}

// 找到链表第一个入环节点，如果无环，返回null
public static Node getLoopNode(Node head) {
  if (head == null || head.next == null || head.next.next == null) {
    return null;
  }
  // n1 慢  n2 快
  Node slow = head.next; // n1 -> slow
  Node fast = head.next.next; // n2 -> fast
  while (slow != fast) {
    if (fast.next == null || fast.next.next == null) {
      return null;
    }
    fast = fast.next.next;
    slow = slow.next;
  }
  // slow fast  相遇
  fast = head; // n2 -> walk again from head
  while (slow != fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow;
}

// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
public static Node noLoop(Node head1, Node head2) {
  if (head1 == null || head2 == null) {
    return null;
  }
  Node cur1 = head1;
  Node cur2 = head2;
  int n = 0;
  while (cur1.next != null) {
    n++;
    cur1 = cur1.next;
  }
  while (cur2.next != null) {
    n--;
    cur2 = cur2.next;
  }
  if (cur1 != cur2) {
    return null;
  }
  // n  :  链表1长度减去链表2长度的值
  cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
  cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
  n = Math.abs(n);
  while (n != 0) {
    n--;
    cur1 = cur1.next;
  }
  while (cur1 != cur2) {
    cur1 = cur1.next;
    cur2 = cur2.next;
  }
  return cur1;
}

// 两个有环链表，返回第一个相交节点，如果不想交返回null
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
  Node cur1 = null;
  Node cur2 = null;
  if (loop1 == loop2) {
    cur1 = head1;
    cur2 = head2;
    int n = 0;
    while (cur1 != loop1) {
      n++;
      cur1 = cur1.next;
    }
    while (cur2 != loop2) {
      n--;
      cur2 = cur2.next;
    }
    cur1 = n > 0 ? head1 : head2;
    cur2 = cur1 == head1 ? head2 : head1;
    n = Math.abs(n);
    while (n != 0) {
      n--;
      cur1 = cur1.next;
    }
    while (cur1 != cur2) {
      cur1 = cur1.next;
      cur2 = cur2.next;
    }
    return cur1;
  } else {
    cur1 = loop1.next;
    while (cur1 != loop1) {
      if (cur1 == loop2) {
        return loop1;
      }
      cur1 = cur1.next;
    }
    return null;
  }
}

7.环形链表

142. 环形链表 II

测试链接：https://leetcode.cn/problems/linked-list-cycle-ii/

数学证明如下：

需要利用数学知识：

相遇时的情况：

假设链表头到环起点的距离为 ( D )。
环的长度为 ( C )。
slow 和 fast 在环内的某个点相遇，设相遇点到环起点的距离为 ( X )。

关键观察：

当相遇时，slow 走的总距离为 D + X。
fast 走的总距离为 \(D + X + k \cdot C\)（因为 fast 可能在环中多跑了几圈，( k ) 是圈数）。
由于 fast 的速度是 slow 的 2 倍，( fast ) 走的距离是 ( slow ) 的 2 倍：\(D + X + k \cdot C = 2 \cdot (D + X)\)
化简：
\[D + X + k \cdot C = 2D + 2X\] \[k \cdot C = D + X\] \[D = k \cdot C - X\]
这表明：从链表头到环起点的距离 ( D ) 和相遇点到环起点的距离（通过环内的路径）有关系。

找到环起点的方法：

当 slow 和 fast 相遇后：
- 将一个指针（比如 slow）放回链表头部。
- 另一个指针（fast）留在相遇点。
- 两个指针以相同速度（每次 1 步）移动。
它们会在环的起点相遇。

为什么有效：

从链表头到环起点走 ( D ) 步。
从相遇点回到环起点（沿环走剩余部分），距离为 C - X（环长减去相遇点到起点的距离）。
根据公式 \(D = k \cdot C - X\)：
- 如果 k = 1，则 D = C - X。
- 两个指针同时走 ( D ) 步：
  - 从头走的指针到达环起点。
  - 从相遇点走的指针沿环走 C - X，正好回到环起点。
因此，它们一定在环起点相遇。(见下图，画的比较抽象)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode q = head, s = head;
        while (q != null && q.next != null && q.next.next != null) {
            q = q.next.next;
            s = s.next;
            if (q == s) {
                q = head;
                while (q != s) {
                    q = q.next;
                    s = s.next;
                }
                return q;
            }
        }
        return null;
    }
}

8.环形链表（续）

能不能不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个点删掉？返回头部（万一要删除的是头部节点）

面试如果真的问这个，也是想问他说的内个抖机灵的做法（将要删除的下一个节点的值给当前这个节点，然后调节当前节点的next指针）。

示例： 链表: A→B→C→D→E 要删除 C（只知道 C）

复制 D 的值到 C。链表变成: A→B→D→D→E (节点 C 存储了 D 的值)

C.next=D.next (指向 E) 链表变成: A→B→D→E

节点 D 被成功移除了，链表保持了 A→B→D→E 的逻辑顺序。

至于最后一个节点怎么办，确实是没有办法的，解释如下。

抖机灵的办法无法完成一种情况：删除链表最后一个节点。null是系统上一个独立的区域。比如1->2->null。如果你要删掉2。你需要找到1，然后将1.next指向这个区域。不是说你把2变成null，你变不成。你就是变成了，1的next也没有指向公认的null的区域。

【体系学习010】链表题目