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 的问题。有两种解法：
把第一个链表的结尾连接到第二个链表的开头，看第二个链表是否存在环；
或者直接比较两个链表的最后一个节点是否相同。
