LeetCode题解——链表

﹏ヽ暗。殇╰゛Y 2023-02-14 13:11 154阅读 0赞

### 文章目录 ###

*   *  相交链表
     *   *  解法
     *  反转链表
     *   *  递归解法
         *  头插法
     *  合并两个有序链表
     *   *  非递归解法
         *  递归解法
     *  删除排序链表中的重复元素
     *   *  解法1
         *  解法2
         *  递归
     *  删除链表的倒数第N个节点
     *   *  解法
     *  两两交换链表中的节点
     *   *  解法
     *  两数相加 II
     *   *  解法
     *  回文链表
     *   *  解法
     *  分隔链表
     *   *  解法
     *  奇偶链表
     *   *  解法
         *   *  推荐阅读

## 相交链表 ##

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：  
![format_png][]  
![format_png 1][]  
![format_png 2][]

### 解法 ###

/**
     * 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 l1 = headA, l2 = headB;
            while (l1 != l2) {
        
                l1 = (l1 == null) ? headB : l1.next;
                l2 = (l2 == null)  ? headA : l2.next;
            }
            return l1;
        }
    }

## 反转链表 ##

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL  
进阶:  
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

### 递归解法 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
            ListNode nextNode = head.next;
            ListNode newHead = reverseList(nextNode);
            nextNode.next = head;
            head.next = null;
            return newHead;
        }
    }

### 头插法 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
            ListNode newHead = new ListNode(-1);
            while (head != null) {
        
                ListNode next = head.next;
                head.next = newHead.next;
                newHead.next = head;
                head = next;
            }
            return newHead.next;
        }
    }

## 合并两个有序链表 ##

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4  
输出：1->1->2->3->4->4

### 非递归解法 ###

每次找到最小结点，接在prev后面即可。

/**
     * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        
            ListNode preHead = new ListNode(-1);
            ListNode prev = preHead;
            while(l1 != null && l2 != null) {
        
                if (l1.val <= l2.val) {
        
                    prev.next = l1;
                    l1 = l1.next;
                } else {
        
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
            prev.next = (l1 == null) ? l2 : l1;
            return preHead.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 mergeTwoLists(ListNode l1, ListNode l2) {
        
            if (l1 == null) {
        
                return l2;
            } else if (l2 == null) {
        
                return l1;
            } else if (l1.val <= l2.val) {
        
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
        
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
            
        }
    }

## 删除排序链表中的重复元素 ##

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2  
输出: 1->2  
示例 2:

输入: 1->1->2->3->3  
输出: 1->2->3

### 解法1 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            if (head == null) {
        
                return null;
            }
            ListNode prev = head, prevHead = prev;
            head = head.next;
            while (head != null) {
        
                if (prev.val != head.val) {
        
                    prev.next = head;
                    prev = prev.next;
                } else {
        
                    prev.next = null;
                }
                head = head.next;
            }
            return prevHead;
        }
    }

### 解法2 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            ListNode current = head;
            while (current != null && current.next != null) {
        
                if (current.val == current.next.val) {
        
                    current.next = current.next.next;
                } else {
        
                    current = current.next;
                }
            }
            return head;
        }
    }

### 递归 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
            head.next = deleteDuplicates(head.next);
            return head.val == head.next.val ? head.next : head;
        }
    }

## 删除链表的倒数第N个节点 ##

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.  
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

### 解法 ###

快慢指针

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            ListNode fast = head;
            while (n-- > 0) {
        
                fast = fast.next;
            }
            if (fast == null) {
        
                return head.next;
            }
            ListNode slow = head;
            while(fast.next != null) {
        
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return head;
        }
    }

## 两两交换链表中的节点 ##

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

### 解法 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
            ListNode newHead = new ListNode(-1);
            newHead.next = head;
            ListNode pre = newHead;
            while(pre.next != null && pre.next.next != null) {
        
                ListNode l1 = pre.next, l2 = pre.next.next;
                ListNode next = l2.next;
                l1.next = next;
                l2.next = l1;
                pre.next = l2;
                pre = l1;
            }
            return newHead.next;
        }
    }

## 两数相加 II ##

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

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

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)  
输出：7 -> 8 -> 0 -> 7

### 解法 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            Deque<Integer> deque1 = buildDeque(l1);
            Deque<Integer> deque2 = buildDeque(l2);
            ListNode head = new ListNode(-1);
            int carry = 0;
            while (!deque1.isEmpty() || !deque2.isEmpty() || carry != 0) {
        
                int x = deque1.isEmpty() ? 0 : deque1.removeFirst();
                int y = deque2.isEmpty() ? 0 : deque2.removeFirst();
                int sum = x + y + carry;
                ListNode node = new ListNode(sum % 10);
                node.next = head.next;
                head.next = node;
                carry = sum / 10;
            }
            return head.next;
        }
        
        public Deque<Integer> buildDeque(ListNode node) {
         // 用deque模拟栈, 因为stack是遗留类，不推荐使用
            Deque<Integer> deque = new LinkedList<>();
            while (node != null) {
        
                deque.addFirst(node.val);
                node = node.next;
            }
            return deque;
        }
    }

## 回文链表 ##

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2  
输出: false  
示例 2:

输入: 1->2->2->1  
输出: true  
进阶：  
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

### 解法 ###

切成两半，把后半段反转，然后比较两半是否相等。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean isPalindrome(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return true;
            }
            ListNode slow = head, fast = head.next;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
            }
            if (fast != null) {
        
                slow = slow.next;
            }
            cut(head, slow);
            return isEqual(head, reverse(slow));
        }
        private boolean isEqual(ListNode l1, ListNode l2) {
        
            while (l1 != null && l2 != null) {
        
                if (l1.val != l2.val) {
        
                    return false;
                }
                l1 = l1.next;
                l2 = l2.next;
            }
            return true;
        }
        private void cut(ListNode head, ListNode cutNode) {
        
            while (head.next != cutNode) {
        
                head = head.next;
            }
            head.next = null;
        }
        private ListNode reverse(ListNode head) {
        
            ListNode newHead = null;
            while (head != null) {
        
                ListNode nextNode = head.next;
                head.next = newHead;
                newHead = head;
                head = nextNode;
            }
            return newHead;
        } 
    }

## 分隔链表 ##

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 \[ \[1\], \[2\], \[3\], \[4\], null \]

示例 1：

输入: 
    root = [1, 2, 3], k = 5
    输出: [[1],[2],[3],[],[]]
    解释:
    输入输出各部分都应该是链表，而不是数组。
    例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
    第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
    最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
    示例 2：
    
    输入: 
    root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
    输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
    解释:
    输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。
     
    
    提示:
    
    root 的长度范围： [0, 1000].
    输入的每个节点的大小范围：[0, 999].
    k 的取值范围： [1, 50].

### 解法 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode[] splitListToParts(ListNode root, int k) {
        
            int total = 0;
            ListNode cur = root;
            while (cur != null) {
        
                total++;
                cur = cur.next;
            }
            int mod = total % k;
            int size = total / k;
            cur = root;
            ListNode[] res = new ListNode[k];
            for (int i = 0; cur != null && i < k; ++i) {
        
                res[i] = cur;
                int curSize = size + (mod-- > 0 ? 1 : 0);
                for (int j = 0; j < curSize - 1; ++j) {
        
                    cur = cur.next;
                }
                ListNode temp = cur.next;
                cur.next = null;
                cur = temp;
            }
            return res;
        }
    }

## 奇偶链表 ##

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL  
输出: 1->3->5->2->4->NULL  
示例 2:

输入: 2->1->3->5->6->4->7->NULL  
输出: 2->3->6->7->1->5->4->NULL  
说明:

应当保持奇数节点和偶数节点的相对顺序。  
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

### 解法 ###

/**
     * 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 oddEvenList(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
            ListNode l1 = head, l2 = head.next, cutNode = head.next;
            while (l2 != null && l1.next.next != null) {
        
                l1.next = l1.next.next;
                l1 = l1.next;
                l2.next = l2.next.next;
                l2 = l2.next;
            }
            l1.next = cutNode;
            return head;
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png 3][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GdTFUdDNjUEExWjNDTmk0VGpoYkVDd2FtRHN1?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9Gdllteml2TnpRUFFqU2x2UVQ2ZmI4WTVpRW1v?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GcXM5aUNfVmE4aUQ5MTc5SW9JaVBIeGFLcXVi?x-oss-process=image/format,png
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9Gc2lzMkxhbzF6UkEtUnBic1RFREEwX3owNHdi?x-oss-process=image/format,png