1.分隔链表（86-中）
问题描述：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。保证两个分区中每个节点的初始相对位置。
案例：
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
思路：这里使用技巧是定义两个虚拟节点，一个负责小于x区域一个负责大于等于x区域，遍历链表，最后对两个分区进行连接。
代码:
public ListNode partition(ListNode head, int x) { if (head == null) return head; ListNode largeHead = new ListNode(x - 1); ListNode large = largeHead; ListNode smallHead = new ListNode(x - 1); ListNode small = smallHead; while (head != null) { if (head.val < x) { small.next = head; small = small.next; } else { large.next = head; large = large.next; } head = head.next; } // 连接两个分区 large.next = null; small.next = largeHead.next; return smallHead.next; }
2.归并两个有序链表（21-中）
题目描述：拼接两个升序链表，保证合并的新链表也是升序。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
思路：本题通过递归和迭代实现。
法1：递归三部曲：
- 递归函数：递归寻找两个链表中较小值依次连接组成的新链表。
- 终止条件：当一个链表遍历结束
- 递归逻辑：比较两个节点值，返回较小值，继续比较两个链表的剩余节点。
法2：迭代实现：实现逻辑相同，注意定义虚拟节点dummyHead，使用cur遍历新链表并连接。
代码：
//解法1：递归 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); // 返回合并的新链表 return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } // 解法2：迭代 public ListNode mergeTwoLists_1(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(-1); ListNode cur = dummyHead; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 == null) ? l2 : l1; return dummyHead.next; }
3.归并k个有序链表（23-难）
题目描述：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
思路：
法1：优先级队列：先对k个有序链表按照头指针升序，每次取小根堆的堆顶作为当前k个链表的最小值。时间复杂度为O(nlogk)，n为所有链表的元素个数，logk为比较k个位置后选择最小值消耗的时间。
法2：类似21题思路，对于k个链表，最朴素的想法就是顺序合并，但是时间复杂度较高顺序合并时间复杂度为O(k^2*n），作为定性分析的话，每个链表被合并了k次。
这里可以使用分治的思路进行优化，每次找一对进行合并，那么第一轮合并之后，k个链表被合并成了 k/2个链表，平均每个链表的长度为2n/k。依次类推重复这个过程，最终链表有序。
分治合并时间复杂度分析：K条链表的总结点数是 N，平均每条链表有 N/K个节点，因此合并两条链表的时间复杂度是 O(N/K)。从 K 条链表开始两两合并成 1条链表，因此每条链表都会被合并 logK次，因此 K条链表会被合并 K * logK 次，因此总共的时间复杂度是 K∗logK∗N/K 即 O（NlogK）。
代码：
//解法1：优先级队列（小根堆） public ListNode mergeKLists(ListNode[] lists) { Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val); for (ListNode node : lists) { if (node != null) { pq.offer(node); } } ListNode dummyHead = new ListNode(-1); ListNode cur = dummyHead; while (!pq.isEmpty()) { ListNode minNode = pq.poll(); cur.next = minNode; cur = minNode; if (minNode.next != null) { pq.offer(minNode.next); } } return dummyHead.next; } // 解法2：分治合并 public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; return merge(lists, 0, lists.length - 1); } // 分治优化 private ListNode merge(ListNode[] lists, int left, int right) { if (left == right) return lists[left]; int mid = left + (right - left) / 2; ListNode l1 = merge(lists, left, mid); ListNode l2 = merge(lists, mid + 1, right); return mergeTwoLists(l1, l2); } // 合并两个有序链表(迭代版-推荐) private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(-1); ListNode cur = dummyHead; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 == null) ? l2 : l1; return dummyHead.next; }
4.链表求和（面试题）
题目描述：对两个由链表表示的非负整数进行求和，返回求和后的链表。进阶：输入链表不可修改！
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7
思路：对于逆序操作问题首先想到栈结构，实现关键点：
- 采用栈结构逆序获取链表值；
- 每一位计算时，考虑上一位进位值
carry； - 创建节点，采用头插法组织链表。
代码：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); while (l1 != null) { stack1.push(l1.val); l1 = l1.next; } while (l2 != null) { stack2.push(l2.val); l2 = l2.next; } int carry = 0; ListNode head = null; while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) { //初始值设置为上一次计算的进位值 int sum = carry; sum += (stack1.isEmpty() ) ? 0 : stack1.pop(); sum += (stack2.isEmpty() ) ? 0 : stack2.pop(); ListNode node = new ListNode(sum % 10); // 头插节点构造链表 node.next = head; head = node; carry = sum / 10; } return head; }
5.找出两个链表的交点（160-易）
题目描述：寻找两个单链表（每个节点只有1个后继节点）相交的起始节点，不想交返回null。
示例：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8
思路：
1.定义两个指针l1, l2，使得单链表A的尾部连接B的头部，B的尾部连接A的头部（即两个单链表构成环）
2.设链表A长a, 链表B长b,两指针同步在链表A和B上移动（ 即a + b ？= b + a）
- 若走完后同时为null，则无交点
- 若中间存在l1=l2，这时指向即为交点（a + b == b + a）
代码：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode l1 = headA, l2 = headB; while (l1 != l2) { l1 = (l1 == null) ? headB : l1.next; l2 = (l2 == null) ? headA : l2.next; } return l1; }
如果只是判断是否存在交点，那么就是另一个问题，即 编程之美 3.6 的问题。有两种解法：
- 把第一个链表的结尾连接到第二个链表的开头，看第二个链表是否存在环；
- 或者直接比较两个链表的最后一个节点是否相同。
