[数据结构与算法]LeetCode链表篇

一、简单题

1、二进制链表转整数

给你一个单链表的引用结点head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的?十进制值?。

思路：每读到一个数放到二进制的低位，相当于原来的二进制左移一位加上读取到的值。

    public int getDecimalValue(ListNode head) {
        int sum = 0;
        while (head != null){
            sum = 2 * sum + head.val;
            head = head.next;
        }
        return sum;
    }

2、环形链表

给你一个链表的头节点?head?，判断链表中是否有环。

思路：快慢指针

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

3、二进制链表转整数?

给你一个单链表的引用结点?head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

    public int getDecimalValue(ListNode head) {
        int sum = 0;
        //往后遍历一个节点相当于二进制左移一位
        while (head != null){
            sum = 2 * sum + head.val;
            head = head.next;
        }
        return sum;
    }

?二、中等题

1、两数相加

给你两个?非空?的链表，表示两个非负的整数。它们每位数字都是按照?逆序?的方式存储的，并且每个节点只能存储?一位?数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

思路：我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 000 。

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode cur = res;
        int carry = 0;
        while (l1 != null || l2 != null){
            int n1 = (l1 == null) ? 0 : l1.val;
            int n2 = (l2 == null) ? 0 : l2.val;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1 != null){
                l1 = l1.next;
            }
            if (l2 != null){
                l2 = l2.next;
            }
        }
        if (carry > 0){
            cur.next = new ListNode(carry);
        }
        return res.next;
    }

2、删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第?n?个结点，并且返回链表的头结点。

思路：添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

通过快慢指针定位倒数第N个节点

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode res = new ListNode(0, head);
        ListNode fast = head;
        ListNode slow = res;
        for (int i = 0;i < n;i++){
            fast = fast.next;
        }
        while (fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return res.next;
    }

3、两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

方法1：迭代

    public ListNode swapPairs(ListNode head) {
        ListNode res = new ListNode(0, head);
        ListNode temp = res;
        while (temp.next != null && temp.next.next != null){
            //保存节点
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            //交换节点
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            //更新节点
            temp = node1;
        }
        return res.next;
    }

方法二：递归?

    public ListNode swapPairs(ListNode head) {
        //递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。
        if (head == null && head.next == null){
            return head;
        }

        ListNode one = head;
        ListNode two = one.next;
        ListNode three = two.next;

        two.next = one;
        one.next = swapPairs(three);

        return two;
    }

4、旋转链表

给你一个链表的头节点?head?，旋转链表，将链表每个节点向右移动?k?个位置。?

简单的方法是闭合成环，自己第一次写使用迭代的方式去实现了，但是时间复杂度比较高。

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0){
            return head;
        }
        ListNode res = new ListNode(0, head);
        // 计算链表长度
        ListNode node = head;
        int n = 0;
        while (node != null){
            node = node.next;
            n++;
        }
        // 当向右移动的次数 k >= n 时，我们仅需要向右移动 k % n 次即可。
        k = k % n;
        
        while (k-- != 0){
            ListNode cur = res.next;
            ListNode pre = cur;
            //找到倒数第二个节点与倒数第一个节点
            while (cur.next != null){
                pre = cur;
                cur = cur.next;
            }
            //倒数第二个节点的next设置为null
            pre.next = null;
            //将倒数第一个节点插入头节点前面
            cur.next = res.next;
            res.next = cur;
        }
        return res.next;
    }

使用快慢指针优化了上面的代码

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0){
            return head;
        }

        // 计算链表长度
        ListNode node = head;
        int n = 0;
        while (node != null){
            node = node.next;
            n++;
        }
        // 当向右移动的次数 k >= n 时，我们仅需要向右移动 k % n 次即可。
        k = k % n;
        if (k == 0){
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;
        // fast先移动 k 步
        for (int i = 0;i < k;i++){
            fast = fast.next;
        }
        // 快慢指针再一起同步前进，直至fast走到尾节点停
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }

        // 此时的慢指针slow的下一个节点就是旋转后的新头，原尾节点fast串连到head上：
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head;

        return newHead;
    }

?官方给出的思路：闭合成环，先将给定的链表连接成环，然后将指定位置断开。

    public ListNode rotateRight3(ListNode head, int k){
        if (head == null || head.next == null || k == 0){
            return head;
        }
        // 计算链表长度
        ListNode iter = head;
        int n = 1;
        while (iter.next != null){
            iter = iter.next;
            n++;
        }

        int add = n - k % n;
        //连接成环
        iter.next = head;

        while (add-- > 0){
            iter = iter.next;
        }

        //找到要断开位置的前一个节点
        ListNode res = iter.next;
        //断开链表
        iter.next = null;
        return res;
    }

5、删除排序链表中的重复元素 II

给定一个已排序的链表的头?head?，?删除原始链表中所有重复数字的节点，只留下不同的数字?。返回?已排序的链表?。?

思路：由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的， 因此我们只需要对链表进行一次遍历，就可以删除重复的元素。由于链表的头节点可能会被删除， 因此我们需要额外使用一个哑节点（dummy node）指向链表的头节点

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null){
            return head;
        }
        ListNode res = new ListNode(0, head);
        ListNode cur = res;
        while (cur.next != null && cur.next.next != null){
            if (cur.next.val == cur.next.next.val){
                int k = cur.next.val;
                while (cur.next != null && cur.next.val == k){
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return res.next;
    }

6、分隔链表

给你一个链表的头节点?head?和一个特定值?x?，请你对链表进行分隔，使得所有?小于?x?的节点都出现在?大于或等于?x?的节点之前。

你应当?保留?两个分区中每个节点的初始相对位置。

思路：维护两个链表 small和 large即可，small链表按顺序存储所有小于 x的节点，large链表按顺序存储所有大于等于 x的节点。遍历完原链表后，我们只要将 small链表尾节点指向 large链表的头节点即能完成对链表的分隔。

    public ListNode partition(ListNode head, int x) {
        //创建两个链表
        ListNode small = new ListNode(0, head);
        ListNode smallHead = small;
        ListNode large = new ListNode(0, head);
        ListNode largeHead = large;

        //维护两个链表，小于x的拼接到small，大于等于x的拼接在large
        while (head != null){
            if (head.val < x){
                small.next = head;
                small = small.next;
            }else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }

        //拼接两个链表
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }

7、反转链表 II

给你单链表的头指针?head?和两个整数?left?和?right?，其中?left <= right?。请你反转从位置?left?到位置?right?的链表节点，返回?反转后的链表?。?

方法一：穿针引线

思路：反转?left?到?right?部分以后，再拼接起来。

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode res = new ListNode(0, head);
        ListNode pre = res;

        //1.从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        for (int i = 0; i < left - 1; i++){
            pre = pre.next;
        }
        //left节点
        ListNode leftNode = pre.next;

        //2.从left节点走 right - left 步，来到 right节点
        ListNode rightNode = leftNode;
        for (int i = 0; i < right - left; i++){
            rightNode = rightNode.next;
        }
        //right节点的下一个节点
        ListNode succ = rightNode.next;

        //3.切断链表
        pre.next = null;
        rightNode.next = null;

        //4.反转链表
        reverse(leftNode);

        //5.接回原来的链表中
        pre.next = rightNode;
        leftNode.next = succ;

        return res.next;
    }

    //翻转链表
    public void reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }

方法二：一次遍历「穿针引线」反转链表（头插法）

方法一的缺点是：如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到 left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次。

思路：每遍历到一个节点，让这个新节点来到反转部分的起始位置。

操作步骤：

• 先将 curr 的下一个节点记录为 next；
• 执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
• 执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
• 执行操作 ③：把 pre 的下一个节点指向 next。

第 1 步完成以后「拉直」的效果如下：?

?

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode res = new ListNode(0, head);
        ListNode pre = res;
        // left节点的前一个节点
        for (int i = 0; i < left - 1; i++){
            pre = pre.next;
        }
        // left节点
        ListNode cur = pre.next;
        ListNode next = null;
        for (int i = 0; i < right - left; i++){
            //保存cur节点的下一个节点
            next = cur.next;
            //让 next 节点来到 pre 节点的后面
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return res.next;
    }

8、环形链表II

给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。

思路：快慢指针法

    public ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            //快慢指针相遇
            if (fast == slow){
                fast = head;
                while (fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

9、重排链表

给定一个单链表?L?的头节点?head?，单链表?L?表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

?方法一：线性表

利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。

    public void reorderList(ListNode head) {
        if (head == null){
            return;
        }
        //将链表存入集合中
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null){
            list.add(temp);
            temp = temp.next;
        }
        int i = 0;
        int j = list.size() - 1;
        //重新拼接链表
        while (i < j){
            list.get(i).next = list.get(j);
            i++;
            //说明已经拼接完成，继续操作会使链表成环
            if (i == j){
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }

方法二：寻找链表中点 + 链表逆序 + 合并链表

    public void reorderList(ListNode head) {
        if (head == null){
            return;
        }
        //1.找到中间节点
        ListNode middle = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = middle.next;
        //分割链表
        middle.next = null;
        //2.反转链表
        l2 = reverse(l2);
        //3.合并链表
        mergeListNode(l1, l2);
    }

    //寻找中间节点
    public ListNode middleNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //翻转链表
    public ListNode reverse(ListNode head){
        ListNode per = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = per;
            per = cur;
            cur = next;
        }
        return per;
    }

    //合并链表
    public void mergeListNode(ListNode l1, ListNode l2){
        ListNode temp1 = l1;
        ListNode temp2 = l2;
        while (l1 != null && l2 != null){
            //保存下一个节点
            l1 = l1.next;
            l2 = l2.next;
            //将l2的节点插入l1
            temp2.next = temp1.next;
            temp1.next = temp2;
            //更新节点
            temp1 = l1;
            temp2 = l2;
        }
    }

10、删除链表中的节点

有一个单链表的?head，我们想删除它其中的一个节点?node。

给你一个需要删除的节点?node?。你将?无法访问?第一个节点??head。

链表的所有值都是?唯一的，并且保证给定的节点?node?不是链表中的最后一个节点。

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

11、奇偶链表

给定单链表的头节点?head?，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是?奇数?，?第二个节点的索引为?偶数?，以此类推。

自己用迭代写的，官方是使用分离节点后合并的方法，实现方式大同小异

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        //存储链表节点
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null){
            list.add(temp);
            temp = temp.next;
        }
        //奇链表拼接
        int i = 0;
        while (i + 2 <= list.size() - 1){
            list.get(i).next = list.get(i = i + 2);
        }
        //偶链表拼接
        int j = 1;
        while (j + 2 <= list.size() - 1){
            list.get(j).next = list.get(j = j + 2);
        }
        //两个链表组合
        list.get(i).next = list.get(1);
        list.get(j).next = null;
        return head;
    }

分离节点后合并

    public ListNode oddEvenList2(ListNode head) {
        if (head == null){
            return head;
        }
        //奇链表头节点
        ListNode odd = head;
        //偶链表头节点
        ListNode evenHead = head.next;
        ListNode even = head.next;
        while (even != null && even.next != null){
            //拼接到奇链表后面
            odd.next = even.next;
            odd = odd.next;
            //拼接到偶链表后面
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

12、两数相加 II

给你两个?非空?链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

思路：和 两数相加I 的链表顺序相反，返回的链表顺序也相反。将两个链表反转就和上一个题一样了，别忘了使用头插法而不是尾插法，大的数字在前面。

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //反转链表
        l1 = reverse(l1);
        l2 = reverse(l2);
        int carry = 0;
        ListNode post = null;
        //相加
        while (l1 != null || l2 != null || carry > 0){
            int a = (l1 == null) ? 0 : l1.val;
            int b = (l2 == null) ? 0 : l2.val;
            int sum = a + b + carry;
            carry = sum / 10;
            //头插法
            ListNode cur = new ListNode(sum % 10);
            cur.next = post;
            post = cur;
            
            if (l1 != null){
                l1 = l1.next;
            }
            if (l2 != null){
                l2 = l2.next;
            }
        }
        return post;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

三、总结

对于链表题，如果想不通如何操作的，可以通过图解去帮助思考，做了几道题后就会慢慢上手。

以下是我写了一些链表题的总结：

1、遇到与中间节点，环形链表相似的问题，可以使用快慢指针

2、对于头节点不确定或者需要操作头节点的情况，添加一个哑节点，即next执向头节点，这样一来，我们就不需要对头节点进行特殊的判断了。

例如：

• 删除链表的倒数第 N 个结点：不确定头节点是否为要删除的节点
• 两两交换链表中的节点：需要操作头节点，添加一个哑节点便很好操作
• 删除排序链表中的重复元素，不确定头节点是否为要删除的节点

3、对于在单个链表操作比较复杂的，可以通过维护新的链表，简化操作

例如：

• 分隔链表：维护两个链表，最终进行拼接
• 局部反转链表：先切断要翻转的链表，翻转后进行拼接
• 重排链表：寻找链表中点 + 链表逆序 + 合并链表
• 奇偶链表：维护两个链表，最终进行拼接