【leetcode题解】链表
目录
链表
两数相加
两两交换链表中的节点
重排链表
合并 K 个升序链表（困难）
K 个一组翻转链表
链表
1. 常用技巧
- 画图！！！（直观+形象，便于我们理解）
- 引入虚拟“头”节点（便于处理边界情况；方便我们对链表进行操作）
- 不要吝啬空间，大胆去定义变量
- 快慢双指针（判环；找链表中环的入口；找链表中倒数第n个节点）
2. 链表中的常用操作
- 创建一个新节点 new
- 尾插
- 头插（逆序链表）
两数相加
2. 两数相加 - 力扣（LeetCode）
/**
* 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 addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur1 = l1, cur2 = l2;
ListNode newHead = new ListNode(0);// 创建一个虚拟头节点，方便记录结果
ListNode prev = newHead;// 尾插操作的尾指针
int t = 0;// 记录进位
while (cur1 != null || cur2 != null || t != 0) {
// 先加上第一个链表
if (cur1 != null) {
t += cur1.val;
cur1 = cur1.next;
}
// 再加上第二个链表
if (cur2 != null) {
t += cur2.val;
cur2 = cur2.next;
}
prev.next = new ListNode(t % 10);
prev = prev.next;
t /= 10;
}
return newHead.next;//
}
}两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣（LeetCode）
解法一：递归
解法二：循环、迭代（模拟）
/**
* 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 swapPairs(ListNode head) {
if (head == null || head.next == null)// 空链表或只有一个结点的链表
return head;
ListNode newhead = new ListNode(0);// 虚拟“头”节点
newhead.next = head;
ListNode prev = newhead, cur = prev.next, next = cur.next, nnext = next.next;
while (cur != null && next != null) {
// 1. 交换节点
prev.next = next;
next.next = cur;
cur.next = nnext;
// 2. 修改指针
prev = cur;// 注意顺序
cur = nnext;
if (cur != null)
next = cur.next;
if (next != null)
nnext = next.next;
}
return newhead.next;
}
}重排链表
143. 重排链表 - 力扣（LeetCode）
解法：模拟
1. 找到链表的中间节点（快慢双指针）
2. 把后面的部分逆序（反转链表：双指针；头插法）
3. 合并两个链表（双指针）
/**
* 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 void reorderList(ListNode head) {
// 处理边界情况
if (head == null || head.next == null || head.next.next == null)
return;
// 找链表的中间节点
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 此时，slow指向中间节点
// 2. 把slow后面的部分逆序 - 头插法
ListNode newhead = new ListNode(0);// 虚拟头节点
ListNode cur = slow.next;//
ListNode prev = null;
slow.next = null;// 把两个链表分离
while (cur != null) {
ListNode next = cur.next;// 保存下一个节点
cur.next = newhead.next;
newhead.next = cur;
cur = next;
}
// 3. 合并两个链表 - 双指针
ListNode cur1 = head, cur2 = newhead.next;
ListNode ret = new ListNode(0);
prev = ret;
while (cur1 != null) {
// 先放第一个链表
prev.next = cur1;
prev = cur1;
cur1 = cur1.next;
// 合并第二个链表
if (cur2 != null) {
prev.next = cur2;
prev = cur2;
cur2 = cur2.next;
}
}
}
}合并 K 个升序链表（困难）
23. 合并 K 个升序链表 - 力扣（LeetCode）
解法一：暴力解法（不推荐）
解法二：利用优先级队列做优化
/**
* 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 mergeKLists(ListNode[] lists) {
// 创建一个小根堆
PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
// 把所有的头节点放进小根堆
for (ListNode head : lists) {
if (head != null)
heap.offer(head);
}
// 合并链表
ListNode ret = new ListNode(0);
ListNode prev = ret;
while (!heap.isEmpty()) {
ListNode t = heap.poll();
prev.next = t;
prev = t;
if (t.next != null)
heap.offer(t.next);
}
return ret.next;
}
}解法三：分治 - 递归
/**
* 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 mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int left, int right) {
if (left > right)
return null;
if (left == right)
return lists[left];
// 平分数组
int mid = (left + right) / 2;
// [left,mid] [mid+1,right]
// 处理左右两部分
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return mergeTwo(l1, l2);
}
public ListNode mergeTwo(ListNode l1, ListNode l2) {
// 合并两个链表
if (l1 == null)
return l2;
if (l2 == null)
return l1;
ListNode head = new ListNode(0);
ListNode cur1 = l1, cur2 = l2, prev = head;
while (cur1 != null && cur2 != null) {
if (cur1.val < cur2.val) {//
prev.next = cur1;
prev = cur1;
cur1 = cur1.next;
} else {
prev.next = cur2;
prev = cur2;
cur2 = cur2.next;
}
}
if (cur1 != null)
prev.next = cur1;
if (cur2 != null)
prev.next = cur2;
return head.next;
}
}K 个一组翻转链表
25. K 个一组翻转链表 - 力扣（LeetCode）
解法：模拟
- 先求出需要逆序多少组：n
- 重复n次，长度为k的链表的逆序即可（头插法）
/**
* 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 reverseKGroup(ListNode head, int k) {
// 1. 先求出需要逆序多少组
int n = 0;
ListNode cur = head;
while (cur != null) {
cur = cur.next;
n++;
}
n /= k;
// 2. 重复n次：长度为k的链表的逆序
ListNode newhead = new ListNode(0);
ListNode prev = newhead;
cur = head;
for (int i = 0; i < n; i++) {
ListNode tmp = cur;
for (int j = 0; j < k; j++) {
// 头插
ListNode next = cur.next;
cur.next = prev.next;
prev.next = cur;
cur = next;
}
prev = tmp;
}
// 把后面不需要逆序的部分连接上
prev.next = cur;
return newhead.next;
}
}