【算法修炼】链表一、二

链表一、二

• • • 链表一
    • • 21、合并两个有序链表（简单）
      • 83、删除排序链表中的重复元素（简单）
      • 82、删除排序链表中的重复元素Ⅱ（中等）
      • 单链表的倒数第K个节点
      • 19、删除链表的倒数第N个节点（中等）
      • 876、链表的中间节点（简单）
      • 链表环检测
      • 链表环检测Ⅱ
      • 160、相交链表（简单）
    • 链表二
    • • 206、反转链表（简单）
      • 反转链表的前n个节点
      • 反转链表的一部分
      • K个一组翻转链表（困难）

前面介绍了树、图等题目的解法，接下来主要对链表相关题目进行讲解和练习。
学习自：https://labuladong.gitee.io/algo/2/18/17/

链表一 21、合并两个有序链表（简单）

题目比较简单，可以直接看代码，主要用到了虚拟头节点dummy，有了dummy可以避免处理空指针的情况，降低代码的复杂性。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        // 指向虚头
        ListNode p = dummy;
        ListNode a = list1, b = list2;
        while (a != null && b != null) {
            if (a.val > b.val) {
                // p.next 指向 b 指向的内存区域
                p.next = b;
                // b不再指向那片内存区域，转去指向b.next的内存区域
                // 但是p.next仍然指向那片内存区域，不影响p.next
                // 注意p.next指向的那片内存区域仍然有b.next!!!
                b = b.next;
            } else {
                p.next = a;
                a = a.next;
            }
            // p移向下一个位置
            p = p.next;
        }
        // 如果两个链表还有剩余的，直接把剩余部分接在后面即可
        if (a != null) {
            p.next = a;
        }
        if (b != null) {
            p.next = b;
        }
        // 虚头的下一个位置就是要返回的值
        return dummy.next;
    }
}

面试常常要求要去重，可以做做下面两道题：

83、删除排序链表中的重复元素（简单）

/**
 * 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 deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode p = head;
        while (p.next != null) {
            if (p.val == p.next.val) {
                p.next = p.next.next;
            } else {
                p = p.next;
            }
        }
        return head;
    }
}

82、删除排序链表中的重复元素Ⅱ（中等）

和上一题不同，本题需要把重复的节点全部进行删除，因为涉及删除头节点，所以最好使用dummy节点，很方便进行重复节点的删除。

链表的题通常需要注意两点：

• 舍得用变量，千万别想着节省变量，否则容易被逻辑绕晕
  head 有可能需要改动时，先增加一个 假head，返回的时候直接取 假head.next，这样就不需要为修改 head 增加一大堆逻辑了。

/**
 * 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 deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;
        while (p.next != null && p.next.next != null) {
            if (p.next.val == p.next.next.val) {
                int x = p.next.val;
                while (p.next != null && p.next.val == x) {
                    p.next = p.next.next;
                }
            } else {
                p = p.next;
            }
        }
        return dummy.next;
    }
}

好了，回到合并两个有序链表，下面还有一个非常经典的问题，合并K个升序链表：

并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？
这里我们就要用到 优先级队列 这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先队列（最小堆）
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
        	@Override
        	public int compare(ListNode a, ListNode b) {
        		return a.val - b.val;
        	}
        });
        // 把链表的头节点加入优先队列
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        }
        while (!pq.isEmpty()) {
            // 获取最小值节点，加到新链表中
            ListNode node = pq.poll();
            p.next = node;
            if (node.next != null) {
                // 下一个节点再入队
                pq.add(node.next);
            }
            // p指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
}

这个算法是面试常考题，它的时间复杂度是多少呢？

优先队列 pq 中的元素个数最多是 k，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)；所有的链表节点都会被加入和d出 pq，所以算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。

单链表的倒数第K个节点

正数的第K个节点很好找，关键是倒数，解决方法类似于快慢指针，首先让两个节点都指向头节点，第一个节点先走k步，然后再让两个节点一起走，直到第一个节点为null，此时第二个节点指向的位置，就是倒数第k个节点的位置。

19、删除链表的倒数第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 removeNthFromEnd(ListNode head, int n) {
        // 快慢指针，第一个先走n步
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 0; i < n; i++) {
            p1 = p1.next;
        }
        ListNode prev = null;
        while (p1 != null) {
            prev = p2;
            p1 = p1.next;
            p2 = p2.next;
        }
        // 此时p2指向的就是倒数第n个节点
        if (head == p2) {
            // 如果删除的是头节点
            return head.next;
        }
        prev.next = prev.next.next;
        return head;
    }
}

优化，由于需要修改头节点，引入dummy节点，删除节点其实需要的是倒数第N+1个节点，所以去找倒数第N+1个节点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 找到倒数第n + 1个节点
        ListNode p1 = dummy;
        ListNode p2 = dummy;
        for (int i = 0; i < n + 1; i++) {
            p1 = p1.next;
        }
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p2.next = p2.next.next;
        return dummy.next;
    }
}

876、链表的中间节点（简单）

经典模板题

/**
 * 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 middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // 快慢指针，快的走两步，慢的走一步，快的=null，慢的指向中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

链表环检测

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

链表环检测Ⅱ

在上一题的基础上，需要找到入环节点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean flag = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                flag = true;
                break;
            }
        }
        if (flag == false) return null;
        // 让其中一个节点从头节点开始走，与另一节点的相遇位置就是入环节点
        slow = head;
        // 判断条件是：slow == fast
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

160、相交链表（简单）

也是双指针，只不过优化方法比较巧妙：当A走完时，让A再去走B；B走完时，B再去走A，这样就可以保证A、B走的步伐一致，如果有交点，它们肯定会同时到达；如果没有交点A、B总会走到尾部null，也是可以的。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        // 如果不相交，p1 p2最后都会走到null，也会退出循环
        while (p1 != p2) {
            if (p1 == null) {
                // 如果A走到头了，继续走B
                p1 = headB;
            } else {
                p1 = p1.next;
            }
            if (p2 == null) {
                // 如果B走到头了，继续走A
                p2 = headA;
            } else {
                p2 = p2.next;
            }
        }
        // 如果是相交的，那么p1!=null
        // 如果不是相交的，那么p1==null,也是可以的
        return p1;
    }
}

链表二

主要是反转链表的考察，递归、迭代都得会。

206、反转链表（简单）

递归写法：




图源：https://labuladong.gitee.io/algo/2/17/17/

写递归函数的关键：相信这个函数、这个函数的作用（返回值）到底是什么，有了这个返回值（作用），我们还需要哪些 *** 作？

/**
 * 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 reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        // 将头节点之后的链表反转，并返回反转后的头节点
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

迭代写法：关键用到了三个指针，刚开始只有cur指针指向头节点，其它都是null，三个指针的交换顺序呈现循环状态。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode nxt = null;
        // 三个指针的交换顺序呈现环状
        while (cur != null) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        // 最后的pre指针就是翻转后的链表的头节点
        return pre;
    }
}

反转链表的前n个节点

递归写法：

和上一题的区别在于head.next = null，因为只用反转前n个节点，所以还有后驱节点要连接，所以head.next = postNode，与后驱节点相连。

class Solution {
    // 记录后驱节点
    ListNode postNode = null;
    public ListNode reverseList(ListNode head, int n) {
        if (n == 1) {
            // 只有一个节点那么说明head.next为后驱节点
            postNode = head.next;
            return head;
        }
        // 以head.next为起点，需要反转前n-1个节点
        ListNode last = reverseList(head.next, n - 1);
        head.next.next = head;
        // 这里需要考虑存在后驱节点
        head.next = postNode;
        return last;
    }
}

反转链表的一部分

递归写法：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            // 如果开始节点为起点，那就直接是返回开始节点的前right个节点
            return reverseN(head, right);
        }
        // 把head.next视作1号节点，那么left、right都要-1
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    // 使用反转前n个节点的函数
    // 反转head开始的前n个节点
    ListNode postNode = null;  // 记录后驱节点
    ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            postNode = head.next;
            return head;
        }
        // 反转以head.next开头的前n - 1个节点
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // 连接到后驱节点
        head.next = postNode;
        return last;
    }
}

迭代写法：

/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

值得一提的是，递归 *** 作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。所以递归 *** 作链表可以作为对递归算法的练习或者拿去和小伙伴装逼，但是考虑效率的话还是使用迭代算法更好。

K个一组翻转链表（困难）

递归写法：
比较好理解，就是分成几个部分进行翻转，每个部分节点数=k，然后每次翻转完成后，把前后两部分连接起来。

图源：https://labuladong.gitee.io/algo/2/17/18/

/**
 * 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) {
        if (head == null) return head;
        ListNode a, b;
        a = head;
        b = head;
        // 先看够不够k个节点
        for (int i = 0; i < k; i++) {
            // 不够k个节点就直接返回
            if (b == null) return head;
            b = b.next;
        }
        // 翻转前k个节点，并得到翻转后的头节点
        ListNode newHead = reverse(a, b);
        // 继续反转接着的k个节点，并与之前的翻转 结果连接起来
        a.next = reverseKGroup(b, k);
        return newHead;
    }
    // 翻转[a,b)的节点
    // 注意这里的翻转不能翻转到b，只能翻转到b的上一个节点
    ListNode reverse(ListNode a, ListNode b) {
        ListNode cur = a;
        ListNode pre = null;
        ListNode nxt = null;
        while (cur != b) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

迭代写法：还没看明白，待更！