【leetcode题解】链表

目录

 链表

两数相加

两两交换链表中的节点

重排链表

合并 K 个升序链表（困难）

K 个一组翻转链表

---

 链表

1. 常用技巧

1. 画图！！！（直观+形象，便于我们理解）
2. 引入虚拟“头”节点（便于处理边界情况；方便我们对链表进行操作）
3. 不要吝啬空间，大胆去定义变量
4. 快慢双指针（判环；找链表中环的入口；找链表中倒数第n个节点）

2. 链表中的常用操作

1. 创建一个新节点 new
2. 尾插
3. 头插（逆序链表）

两数相加

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）

解法：模拟

1. 先求出需要逆序多少组：n
2. 重复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;}
}