---

链表题目练习

两数相加

坑:

• 两个链表都遍历完后,可能需要进位.

    class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 = l1;ListNode cur2 = l2;ListNode head = new ListNode(0);ListNode tail = head;int sum = 0;while (cur1 != null || cur2 != null) {ListNode newNode = new ListNode();tail.next = newNode;tail = newNode;if (cur1 != null) {sum += cur1.val;cur1 = cur1.next;}if (cur2 != null) {sum += cur2.val;cur2 = cur2.next;}if (sum >= 10) {newNode.val = sum % 10;sum = 1;} else {newNode.val = sum;sum = 0;}}// 遍历完两个链表 处理一下进位if (sum != 0) {ListNode newNode = new ListNode(sum);tail.next = newNode;}return head.next;}}

题解代码:

    class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 = l1, cur2 = l2;ListNode head = new ListNode();ListNode tail = head;int sum = 0;while (cur1 != null || cur2 != null || sum != 0) {if (cur1 != null) {sum += cur1.val;cur1 = cur1.next;}if (cur2 != null) {sum += cur2.val;cur2 = cur2.next;}ListNode newNode = new ListNode(sum % 10);tail.next = newNode;tail = newNode;sum /= 10;}return head.next;}}

两两交换链表中的节点

简简单单,一遍过~

草图 :

    class Solution {public ListNode swapPairs(ListNode head) {ListNode virtualHead = new ListNode();virtualHead.next = head;ListNode cur = head, prev = virtualHead;while (cur != null && cur.next != null) {ListNode next = cur.next;prev.next = next;cur.next = next.next;next.next = cur;prev = cur;cur = cur.next;}return virtualHead.next;}}

重排链表

没想出来,看题解思路懂哩~

分成三步走：

1. 找到原链表的中间节点（可以使用快慢指针解决）。
2. 将原链表的右半部分翻转。
3. 将原链表的两端合并。
   • 因为两链表的长度相差不超过 1，所以可以直接合并~

磕磕绊绊总算是写出来了~
看似是一道题，其实是三道题~

在合并两个链表时卡了一下.

坑:

• 前面有指针指向 中间节点 ,链表翻转后指针的指向大概是这样的
  

class Solution {public void reorderList(ListNode head) {// 寻找中间节点ListNode fast = head, slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}// 此时 slow 为中间节点// 翻转 slow 以及 slow 后面的节点ListNode behind = new ListNode();ListNode cur = slow;while (cur != null) {ListNode next = cur.next;cur.next = behind.next;behind.next = cur;cur = next;}// 合并两个链表ListNode cur1 = head, cur2 = behind.next;while (cur2.next != null && cur1.next != null) {ListNode next1 = cur1.next, next2 = cur2.next;cur2.next = next1;cur1.next = cur2;cur1 = next1;cur2 = next2;}}
}

看了题解之后,发现可以把整个链表拆成两份.
而且,发现从中间节点的后一个开始翻转链表也可以过,这样就可以在中间节点这个位置把链表分成两份:

• 一份是 中间节点之前(包含中间节点)
• 另一份是 中间节点之后

题解代码:

    class Solution {public void reorderList(ListNode head) {// 1.寻找中间节点ListNode slow = head, fast = slow;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}ListNode head2 = new ListNode(-1);// 2.逆序 head2 链表ListNode cur = slow.next;// 拆分成两个链表slow.next = null;while (cur != null) {ListNode next = cur.next;cur.next = head2.next;head2.next = cur;cur = next;}// 3. 合并两个链表ListNode head3 = new ListNode(-1);ListNode cur2 = head;ListNode cur3 = head2.next;ListNode prev = head3;while (cur2 != null) {prev.next = cur2;prev = cur2;cur2 = cur2.next;if (cur3 != null) {prev.next = cur3;prev = cur3;cur3 = cur3.next;}}}}

合并 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 {private ListNode mergeLists(ListNode l1, ListNode l2) {if (l1 == null)return l2;if (l2 == null)return l1;ListNode head = new ListNode(-1);ListNode cur1 = l1, cur2 = l2, tail = head;while (cur1 != null && cur2 != null) {if (cur1.val <= cur2.val) {tail.next = cur1;tail = cur1;cur1 = cur1.next;} else {tail.next = cur2;tail = cur2;cur2 = cur2.next;}}while (cur1 != null) {tail.next = cur1;tail = cur1;cur1 = cur1.next;}while (cur2 != null) {tail.next = cur2;tail = cur2;cur2 = cur2.next;}return head.next;}public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;if (n <= 0)return null;ListNode head = lists[0];for (int i = 1; i < n; i++) {head = mergeLists(head, lists[i]);}return head;}
}

方法二: 使用优先级队列优化.

• 给每个链表都指定一个指针(用来遍历链表),把每一个指针指向的节点放到优先级队列里.不断取出值最小的那个节点,尾插到结果链表中.

忘了怎么在java中自定义排序优先级队列了。

/*** 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) {int n = lists.length;if (n == 0)return null;// 指针数组ListNode[] arr = new ListNode[n];// 默认是小根堆PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {@Overridepublic int compare(ListNode o1, ListNode o2) {return o1.val - o2.val;}});// 结果ListNode ret = new ListNode(-1);ListNode tail = ret;// 把指针对应起来for (int i = 0; i < n; i++) {arr[i] = lists[i];}for (int i = 0; i < n; i++) {if (arr[i] != null) {heap.add(arr[i]);}}while (!heap.isEmpty()) {// 最小的出堆ListNode min = heap.poll();// 拼到结果后面tail.next = min;tail = tail.next;if (min.next != null) {// 不为空，入堆heap.add(min.next);}}return ret.next;}
}

看了题解代码后，发现自己写的代码浪费了很多空间，我为什么要 new 一个指针数组？？？

题解代码：

        /*** 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) {int n = lists.length;if (n == 0)return null;// 1. 创建一个小根堆PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);// 2. 把所有的头结点放进小根堆中for (ListNode head : lists) {if (head != null)heap.offer(head);}// 3.合并链表ListNode ret = new ListNode(-1);ListNode tail = ret;while (!heap.isEmpty()) {// 最小的出堆ListNode min = heap.poll();// 拼到结果后面tail.next = min;tail = tail.next;if (min.next != null) {// 不为空，入堆heap.add(min.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 mergeLists(ListNode l1, ListNode l2) {if (l1 == null)return l2;if (l2 == null)return l1;ListNode head = new ListNode(-1);ListNode tail = head;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {tail.next = l1;l1 = l1.next;} else {tail.next = l2;l2 = l2.next;}tail = tail.next;}while (l1 != null) {tail.next = l1;l1 = l1.next;tail = tail.next;}while (l2 != null) {tail.next = l2;l2 = l2.next;tail = tail.next;}return head.next;}// 递归public ListNode merge(ListNode[] lists, int start, int end) {if (start >= end)return lists[start];int mid = start + (end - start) / 2;ListNode l1 = merge(lists, start, mid);ListNode l2 = merge(lists, mid + 1, end);return mergeLists(l1, l2);}public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;if (n == 0)return null;return merge(lists, 0, n - 1);}}

自己的代码中的合并两个有序链表的代码写的不是很好，最后的 while 可以换成 if 来写的，这是链表，不是数组，不用循环那么多次。。

题解代码：

        /*** 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 mergeLists(ListNode l1, ListNode l2) {if (l1 == null)return l2;if (l2 == null)return l1;ListNode head = new ListNode(-1);ListNode tail = head;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {tail.next = l1;l1 = l1.next;} else {tail.next = l2;l2 = l2.next;}tail = tail.next;}if (l1 != null)tail.next = l1;if (l2 != null)tail.next = l2;return head.next;}// 递归public ListNode merge(ListNode[] lists, int start, int end) {if (start >= end)return lists[start];// 1. 平分数组int mid = start + (end - start) / 2;// 2. 递归处理左右两个部分ListNode l1 = merge(lists, start, mid);ListNode l2 = merge(lists, mid + 1, end);// 3. 合并两个有序链表return mergeLists(l1, l2);}public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;if (n == 0)return null;return merge(lists, 0, n - 1);}}

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 reverse(ListNode head, int k) {ListNode phead = new ListNode(-1);ListNode cur = head, next = cur.next;while (k-- > 0) {cur.next = phead.next;phead.next = cur;cur = next;if (next != null)next = next.next;elsebreak;}return phead.next;}public ListNode reverseKGroup(ListNode head, int k) {ListNode phead = new ListNode(-1);phead.next = head;ListNode slow = phead, fast = head;while (fast != null) {int tmp = k;while (tmp > 0) {if (fast == null) {break;}fast = fast.next;tmp--;}if (tmp > 0)break;slow.next = reverse(slow.next, k);tmp = k;// 写成这样你要清楚：// 等出循环的时候 tmp = -1// 因为在最后一次的判断时 tmp 也要 --while (tmp-- > 0) {slow = slow.next;}slow.next = fast;}return phead.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 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(-1);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;}// 处理剩下的节点不够 k 个的情况prev.next = cur;return newHead.next;}
}

---

总结

链表常用技巧 :

1. 画图是个好东西（感觉好像已经说过好几遍了）.
2. 可以引入一个头结点
   • 便于处理边界情况
   • 方便我们对链表操作
3. 在插入新节点时,可以先把新节点的指针指向都调整好.然后再去调整前一个节点和后一个节点.
   或者直接新建一个指针,指向后一个节点,这样更容易操作~
4. 有时候会用到快慢双指针

---

本文到这里就结束啦~