算法: 链表题目练习
文章目录
- 链表题目练习
- 两数相加
- 两两交换链表中的节点
- 重排链表
- 合并 K 个升序链表
- K 个一组翻转链表
- 总结
链表题目练习
两数相加
坑:
- 两个链表都遍历完后,可能需要进位.
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，所以可以直接合并~
磕磕绊绊总算是写出来了~
看似是一道题，其实是三道题~
在合并两个链表时卡了一下.
坑:
- 前面有指针指向 中间节点 ,链表翻转后指针的指向大概是这样的
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>() {
@Override
public 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;
else
break;
}
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;
}
}
总结
链表常用技巧 :
- 画图是个好东西（感觉好像已经说过好几遍了）.
- 可以引入一个头结点
- 便于处理边界情况
- 方便我们对链表操作
- 在插入新节点时,可以先把新节点的指针指向都调整好.然后再去调整前一个节点和后一个节点.
或者直接新建一个指针,指向后一个节点,这样更容易操作~ - 有时候会用到快慢双指针
本文到这里就结束啦~
