算法细节系列（31）：链表
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434797
算法细节系列（31）：链表
详细代码可以fork下Github上leetcode项目，不定期更新。
题目摘自leetcode：
- Leetcode 206. Reverse Linked List
- Leetcode 025. Reverse Nodes in k-Group
- Leetcode 148. Sort List
- Leetcode 082. Remove Duplicates from Sorted List II
- Leetcode 002. Add Two Numbers
- Leetcode 138. Copy List with Random Pointer
- Leetcode 143. Reorder List
- Leetcode 061. Rotate List
Leetcode 206. Reverse Linked List
思路：
遍历的同时把指针反向，最后就能得到一个reversed List。
代码如下：（迭代版本）
public ListNode reverseList(ListNode head){
if (head == null) return null;
ListNode newHead = null;
while (head != null){
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}递归版本：
public ListNode reverseList(ListNode head){
return recurrsive(head, null);
}
private ListNode recurrsive(ListNode head, ListNode newHead){
if (head == null) return newHead;
ListNode next = head.next;
head.next = newHead;
return recurrsive(next, head);
}Leetcode 025. Reverse Nodes in k-Group
第一题的升级版，采用递归，无非要加入k的一个循环判断，超过k的链表进行翻转，有趣的是此时的newHead，就是递归返回的结果。
代码如下：
public ListNode reverseKGroup(ListNode head, int k) {
return recurrsive(head, k);
}
private ListNode recurrsive(ListNode head, int k) {
ListNode last = head;
int count = 0;
while (last != null && count != k){
last = last.next;
count++;
}
if (count == k){
ListNode newHead = recurrsive(last, k);
for (int i = 0; i < k; i++){
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
head = newHead;
}
return head;
}Leetcode 148. Sort List
采用归并，List在分裂时需要O(n)，最终采用归并就能O(nlogn)O(n \log n)了？不明白。分治起初采用的是计数的方法，但需要遍历n+n/2n + n/2次，优化采用快慢指针，始终以两倍的速度跑到指针末尾，那么慢指针所指向的Node，必然是第二个list的开始。
快慢指针有点并发的味道，while循环中两指针没有相互依赖关系，就好像在一个平行世界中蹦跑一样，直观上更加效率的原因。
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head;
ListNode fast = head;
ListNode prev = null;
while (fast != null && fast.next != null){
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
return merge(sortList(head), sortList(slow));
}
private ListNode merge(ListNode sorted1, ListNode sorted2){
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (sorted1 != null && sorted2 != null){
if (sorted1.val < sorted2.val){
curr.next = sorted1;
sorted1 = sorted1.next;
}else{
curr.next = sorted2;
sorted2 = sorted2.next;
}
curr = curr.next;
}
if (sorted1 != null){
curr.next = sorted1;
}
if (sorted2 != null){
curr.next = sorted2;
}
return dummy.next;
}Leetcode 082. Remove Duplicates from Sorted List II
我的思路：
- 两次遍历，第一次统计所有结点出现的次数。（区分dup结点和非dup结点）
- 遇到非dup结点，直接加入链表，遇到dup结点，跳过。
代码如下：
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return head;
Map<Integer,Integer> map = new HashMap<>();
ListNode pos = head;
while (pos != null){
map.put(pos.val, map.getOrDefault(pos.val, 0) + 1);
pos = pos.next;
}
ListNode dummy = new ListNode(Integer.MAX_VALUE);
ListNode cur = dummy;
pos = head;
while (pos != null){
int cnt = map.get(pos.val);
if (cnt >= 2){ //duplicate
cur.next = pos.next;
pos = pos.next;
}
else{
cur.next = pos;
pos = pos.next;
cur = cur.next;
}
}
return dummy.next;
}需要克服直接扫描的恐惧啊，这样就能在一个循环内解决战斗了。遇到dup直接pos = pos.next，直到下一个位置不再相等，代码如下：
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode dummy = new ListNode(0);
ListNode slow = dummy, fast = head;
slow.next = fast;
while (fast != null){
while (fast.next != null && fast.val == fast.next.val) fast = fast.next;
if (slow.next != fast){ //dup
slow.next = fast.next;
fast = fast.next;
}else{
slow = slow.next;
fast = fast.next;
}
}
return dummy.next;
}slow.next 连接的都是待检测的内容，如果pos位置没有移动（无重复元素，slow.next == fast），两指针均后移，而当出现重复元素，则slow.next指向下一个待检测区域fast.next，且让fast = fast.next，模拟一遍就好了。
Leetcode 002. Add Two Numbers
很简单，维护一个carry就好了，我的思路比较直接，如果l1和l2任何一个为空，直接跳出while循环，转向单纯的plus。代码相对复杂，plus采用递归，为了解决进位溢出，需要加入一些边界判断。
代码如下：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null && l2 != null){
int a1 = l1.val;
int a2 = l2.val;
int a3 = a1 + a2 + carry;
carry = a3 / 10;
ListNode node = new ListNode(a3 % 10);
cur.next = node;
cur = cur.next;
l1 = l1.next;
l2 = l2.next;
}
if (l1 != null){
cur.next = plus(carry, l1);
}
if (l2 != null){
cur.next = plus(carry, l2);
}
if (l1 == null && l2 == null && carry == 1){
cur.next = new ListNode(1);
}
return dummy.next;
}
private ListNode plus(int val,ListNode l1){
if (l1 == null){
return new ListNode(val);
}
if (l1.val + val != 10){
l1.val = l1.val + val;
return l1;
}else{
ListNode ans = new ListNode(0);
ans.next = plus(1, l1.next);
return ans;
}
}简化思路，l1和l2其中的某个到达了链表尾，可以看成与0相加。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null){
int a1 = l1 != null ? l1.val : 0;
int a2 = l2 != null ? l2.val : 0;
int a3 = a1 + a2 + carry;
carry = a3 / 10;
ListNode node = new ListNode(a3 % 10);
cur.next = node;
cur = cur.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry == 1) cur.next = new ListNode(1);
return dummy.next;
}Leetcode 138. Copy List with Random Pointer
直观的想法：
copy需要记录node和index之间的关系，所以一个map用来维护pos和index的关系，方便寻找当前node所在的下标。另一个map用来维护index和pos的关系，方便根据index找当前的pos，相当于一个双向map，可以通过value找index，也可以通过index找value。
代码如下：
public RandomListNode copyRandomList(RandomListNode head) {
RandomListNode dummy = new RandomListNode(0);
RandomListNode cur = dummy;
RandomListNode pos = head;
Map<Integer, RandomListNode> index = new HashMap<>();
Map<RandomListNode, Integer> originIndex = new HashMap<>();
int cnt = 0;
while (pos != null){
cur.next = new RandomListNode(pos.label);
originIndex.put(pos, cnt);
index.put(cnt++, cur.next);
cur = cur.next;
pos = pos.next;
}
pos = head;
cur = dummy.next;
while (pos != null){
if (pos.random != null){
int idx = originIndex.get(pos.random);
cur.random = index.get(idx);
}
cur = cur.next;
pos = pos.next;
}
return dummy.next;
}可以简化代码么？其实之所以叫深度拷贝的原因是一个节点的引用关系也要拷贝。而此题的特点在于每个结点都是RandomListNode，且RandomListNode中的引用关系也是RandomListNode，所以我们完全可以建立 原始node和克隆node的一一对应关系。现在无非就是根据原始node找到相应位置的克隆node把引用关系加上即可。
代码如下：
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return null;
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode pos = head;
while (pos != null){
map.put(pos, new RandomListNode(pos.label));
pos = pos.next;
}
pos = head;
while (pos != null){
map.get(pos).next = map.get(pos.next);
map.get(pos).random = map.get(pos.random);
pos = pos.next;
}
return map.get(head);
}代码简洁很多。
空间复杂度为O(n)O(n)，看了dicuss发现还能优化空间复杂度，核心思想和Map保存位置关系差不多，无非就是利用相对位置，来记录random的随机指针。看图：
蓝色结点为旧结点，红色结点为新结点，如果我们把链表改成这种形式，就可以根据蓝色和红色的相对位置来给红色结点的random指针进行赋值。
思路：
- 构造新旧结点交替的链表
- 复制随机指针，因为相对位置清楚，所以很容易复制（该算法的核心）
- 抽取新旧结点，还原链表。
代码如下：
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return null;
RandomListNode pos = head;
while (pos != null){
RandomListNode copy = new RandomListNode(pos.label);
copy.next = pos.next;
pos.next = copy;
pos = pos.next.next;
}
pos = head;
while (pos != null){
pos.next.random = pos.random != null ? pos.random.next : null;
pos = pos.next.next;
}
pos = head;
RandomListNode copy = pos.next;
RandomListNode curr = copy;
while (pos != null){
pos.next = pos.next.next;
pos = pos.next;
curr.next = pos != null ? pos.next : null;
curr = curr.next;
}
return copy;
}以相对位置来记录链表新旧结点的对应关系很新颖，省去了map的记录。
Leetcode 143. Reorder List
思路：
- 链表对半分成两部分，记为l1和l2
- 对l2进行逆序
- 合并 l1 和 l2，注意合并的规则
代码如下：
public void reorderList(ListNode head) {
if (head == null || head.next == null)
return;
ListNode slow = head, fast = head;
ListNode prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
ListNode reverse = reverse(slow);
merge(head, reverse);
}
private void merge(ListNode l1, ListNode l2) {
while (l1 != null) {
ListNode n1 = l1.next, n2 = l2.next;
l1.next = l2;
if (n1 == null)
break;
l2.next = n1;
l1 = n1;
l2 = n2;
}
}
private ListNode reverse(ListNode head) {
if (head == null)
return null;
ListNode newHead = null;
ListNode pos = head;
while (pos != null) {
ListNode next = pos.next;
pos.next = newHead;
newHead = pos;
pos = next;
}
return newHead;
}合并操作重在把握操作指针，而不是在赋值，容易出错。
Leetcode 061. Rotate List
思路：
找到旋转的四个位置即可，首先遍历一遍链表得到长度，判断k是否超出链表的长度，超出的部分让k = i - k % i，最后进行旋转即可。
代码如下：
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) return head;
int i = 1;
ListNode fast = head, slow = head;
while (fast != null && fast.next != null){
fast = fast.next;
i++;
}
for (int j = i - k % i; j > 1; --j){
slow = slow.next;
}
ListNode dummy = new ListNode(0);
fast.next = head;
dummy.next = slow.next;
slow.next = null;
return dummy.next;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年06月07日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录