目录
- 一、链表常用技巧与操作总结
- 二、2.两数相加
- 三、24.两两交换链表中的节点
- 3.1 迭代
- 3.2 递归
- 四、143.重排链表
- 五、23.合并K个升序链表
- 5.1 堆
- 5.2 分治
- 5.3 暴力枚举
- 六、25.K个⼀组翻转链表
一、链表常用技巧与操作总结
技巧：
- 画图解题。
- 使用虚拟头结点。
- 像有插入类似操作时，直接定义变量，不用考虑节点丢失情况。
- 快慢指针。
操作：
- 创建新节点。
- 尾插。
- 头插。
二、2.两数相加
题目链接：2.两数相加
题目描述：
题目解析：
- 给你两个链表，每个链表都表示一个逆位的数，将两个数相加。
- 相加后的结果不会出现，链表最后节点为0的情况。
解题思路：
- 模拟两个数字相加即可。
- 遍历两个链表，对应节点值相加，放在一个变量sum中，结果链表就接上sum%10的节点，sum / 10表示进位的数。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode newHead = new ListNode(0);//虚拟头结点
ListNode pre = newHead;
int sum = 0;
while(l1 != null || l2 != null || sum != 0) {
if(l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if(l2 != null) {
sum += l2.val;
l2 = l2.next;
}
pre.next = new ListNode(sum % 10);
pre = pre.next;
sum /= 10;
}
return newHead.next;
}
}
三、24.两两交换链表中的节点
题目链接：24.两两交换链表中的节点
题目描述：
题目解析：
- 就交换两个相邻节点即可。
3.1 迭代
解题思路：
- 直接就交换节点即可，为避免节点丢失情况，我们就将交换过程涉及到的节点定义出来即可，然后根据交换后节点直接一一连接即可。
- 交换之后移动这四个变量即可，循环交换就可以了。
- 循环结束条件：当偶数节点个数的时候cur1为null时就该结束了。当奇数节点个数的时候cur2为null时结束。
- 细节处理：当我们第一次定义变量的时候，为防止空指针异常，要将链表为空和链表为1个节点情况排除。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
ListNode newHead = new ListNode(0);
newHead.next = head;
ListNode pre = newHead;
ListNode cur1 = pre.next;
ListNode cur2 = cur1.next;
ListNode last = cur2.next;
while(cur1 != null && cur2 != null) {
//交换
pre.next = cur2;
cur2.next = cur1;
cur1.next = last;
//向后移动
pre = cur1;
if(pre.next == null) break;
cur1 = pre.next;
if(cur1.next == null) break;
cur2 = cur1.next;
last = cur2.next;
}
return newHead.next;
}
}
3.2 递归
解题思路
- 我们就交换两个节点，然后剩余节点又是一个待交换节点的链表。
- 结束条件：链表为空或链表为1个节点。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
ListNode newHead = head.next;
head.next = newHead.next;
newHead.next = head;
head.next = swapPairs(head.next);
return newHead;
}
}
四、143.重排链表
题目链接：143.重排链表
题目描述：
题目分析：
- 就是将链表按照题目给的规则重新排序。
解题思路：
- 这道题其实就可以看成下面的3个步骤：
- 先找到中间节点，再将后半部分链表逆置，再将两个子链表分别取一个节点的连接在一起。
- 找到中间节点：使用快慢双指针。
- 后半部分链表逆置：逆置采用头插法逆置，但是从哪里开始逆置有说法：像下图由于节点数奇偶性不同，slow走到位置不同（可能是正中间节点，也可能是下一个节点）。我们有两个逆置方案
-
- 方案一：将slow以及其后节点都逆置。
-
- 方案二：将slow后的节点逆置。因为本来slow和slow前一个节点在结果链表中的位置是不会变的。
- 因为方便处理两个链表不循环，要让两个子链表末尾都指向null，方案一还需要去记录slow前一个节点，所以采取方案二。
- 将两个子链表合并：直接连接即可。由于采取方案二，所以子链表1一定更长，使用这个当循环条件。
- 细节问题：当链表有1个和2个节点时，不需要交换，并且会导致空指针异常，单独处理。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public void reorderList(ListNode head) {
if(head.next == null || head.next.next == null) return ;
//快慢双指针 找到中间节点
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
//头插法 逆置
ListNode head2 = new ListNode(0);
ListNode cur = slow.next;
slow.next = null;
while(cur != null) {
ListNode next = cur.next;
cur.next = head2.next;
head2.next = cur;
cur = next;
}
head2= head2.next;
//合并两个链表
ListNode newHead = new ListNode(0);
ListNode pre = newHead;
while(head != null) {
if(head != null) {
pre.next = head;
head = head.next;
pre = pre.next;
}
if(head2 != null) {
pre.next = head2;
head2 = head2.next;
pre = pre.next;
}
}
head = newHead.next;
}
}
五、23.合并K个升序链表
题目链接：23.合并K个升序链表
题目描述：
题目解析：
- 给一个链表数组，将元素合并为一个链表，按照升序排列。
5.1 堆
解题思路：
- 我们只需要使用一个小根堆来存储每次需要比较大小的节点，然后将最小的节点尾插放进结果链表。在将最小节点的后一个节点放入堆中即可。
- 入堆的时候，需要判断节点是不是为空，空节点不能进入堆。
- 当堆变空时，就完成合并了。
解题代码：
//时间复杂度：O(N*K*logK)
//空间复杂度：O(k)
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>((l1,l2) -> l1.val-l2.val);
ListNode ret = new ListNode(0);
ListNode pre = ret;
for(ListNode head : lists) {
if(head != null) heap.offer(head);
}
while(!heap.isEmpty()) {
ListNode cur = heap.poll();
pre.next = cur;
pre = pre.next;
cur = cur.next;
if(cur != null) heap.offer(cur);
}
return ret.next;
}
}
5.2 分治
解题思路：
- 与归并排序思路一模一样。
- 直接将数组拆分为两份，两份合并之后得到两个有序链表，再合并两个有序链表即可。
- 细节：链表数组可能为空，也可能是数组内元素为空，所以归并结束条件有所不同。
解题代码：
//时间复杂度：O(N*K*logK)
//空间复杂度：O(k)
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return mrege(0, lists.length-1,lists);
}
public ListNode mrege(int left, int right, ListNode[] lists) {
if(left > right) return null;
if(left == right) return lists[left];
//分：分成两个区间
int mid = (left + right) / 2;
ListNode head1 = mrege(left, mid, lists);
ListNode head2 = mrege(mid+1, right, lists);
//合并两个有序链表
return add(head1,head2);
}
public ListNode add(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode newHead = new ListNode(0);
ListNode pre = newHead;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
pre.next = l1;
pre = pre.next;
l1 = l1.next;
} else {
pre.next = l2;
pre = pre.next;
l2 = l2.next;
}
}
if(l1 != null) pre.next = l1;
if(l2 != null) pre.next = l2;
return newHead.next;
}
}
5.3 暴力枚举
解题思路：
- 直接遍历数组，拆分为k-1次合并两个有序链表即可。
//时间复杂度：O(N*K*K)
//空间复杂度：O(1)
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0) return null;
ListNode ret = lists[0];
for(int i = 1; i < lists.length; i++) {
ret = add(ret, lists[i]);
}
return ret;
}
public ListNode add(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode newHead = new ListNode(0);
ListNode pre = newHead;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
pre.next = l1;
pre = pre.next;
l1 = l1.next;
} else {
pre.next = l2;
pre = pre.next;
l2 = l2.next;
}
}
if(l1 != null) pre.next = l1;
if(l2 != null) pre.next = l2;
return newHead.next;
}
}
六、25.K个⼀组翻转链表
题目链接：25.K个⼀组翻转链表
题目描述：
题目解析：
- 将链表每k个节点逆序，不足k个时不逆序。
解题思路：
- 我们先遍历链表求出节点个数，再除以k得到翻转次数。
- 然后再头插翻转即可。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int n = 0;
ListNode cur = head;
while(cur != null) {
n++;
cur = cur.next;
}
n /= k;
cur = head;
ListNode ret = new ListNode(0);
ListNode pre = ret;
for(int i = 0; i < n; i++) {
ListNode tmp = cur;
for(int j = 0; j < k; j++) {
ListNode next = cur.next;
cur.next = pre.next;
pre.next = cur;
cur = next;
}
pre = tmp;
}
pre.next = cur;
return ret.next;
}
}
