链表相关算法.md

目录

• 2. 两数相加
• 19.删除链表的倒数第 N 个结点
• 21. 合并两个有序链表
• 24. 两两交换链表中的节点
• 61. 旋转链表
• 86. 分隔链表
• 92. 反转链表 II
• 141. 环形链表
• 160. 相交链表
• 206. 反转链表
• 206 反转链表 扩展
• 234. 回文链表
• 237. 删除链表中的节点
• 445. 两数相加 II
• 面试题 02.02. 返回倒数第 k 个节点
• 面试题 02.08. 环路检测
• 剑指 Offer 06. 从尾到头打印链表
• 剑指 Offer 18. 删除链表的节点
• 剑指 Offer 22. 链表中倒数第k个节点
• 剑指 Offer 35. 复杂链表的复制

题目

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

2. 两数相加

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Queue<Integer> queue1 = new LinkedList<>();
    Queue<Integer> queue2 = new LinkedList<>();
    ListNode node1 = l1, node2 = l2;
    while (node1 != null && node2 != null) {
        queue1.offer(node1.val);
        node1 = node1.next;
        queue2.offer(node2.val);
        node2 = node2.next;
    }

    boolean b = false;
    ListNode head = null;
    ListNode p = null;
    while (!queue1.isEmpty() && !queue2.isEmpty()) {
        int result = queue1.poll() + queue2.poll();
        ListNode node = new ListNode((result + (b ? 1 : 0)) % 10);
        if (head == null) {
            head = node;
            p = node;
        } else {
            p.next = node;
            p = node;
        }
        b = result + (b ? 1 : 0) >= 10;
    }

    while (node1 != null) {
        ListNode node = new ListNode((node1.val + (b ? 1 : 0)) % 10);
        p.next = node;
        p = node;
        b = node1.val + (b ? 1 : 0) >= 10;
        node1 = node1.next;
    }

    while (node2 != null) {
        ListNode node = new ListNode((node2.val + (b ? 1 : 0)) % 10);
        p.next = node;
        p = node;
        b = node2.val + (b ? 1 : 0) >= 10;
        node2 = node2.next;
    }
    if (b) {
        p.next = new ListNode(1);
    }
    return head;
}

19. 删除链表的倒数第 N 个结点

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

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

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：

输入：head = [1], n = 1 输出：[] 示例 3：

输入：head = [1,2], n = 1 输出：[1]

解题思路

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode l1 = head;
        ListNode l2 = head;
        for (int i = 0; i < n; i++) {
            l2 = l2.next;
        }
        // p2为null说明n与链表长度等长，因此需要移除第一个元素，故直接返回p1.next即可。
        if (l2 == null) {
            return head.next;
        }
        while (l2.next != null) {
            l1 = l1.next;
            l2 = l2.next;
        }
        l1.next = l1.next.next;
        return head;
    }

Leetcode 21. 合并两个有序链表

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 示例 2：

输入：l1 = [], l2 = [] 输出：[] 示例 3：

输入：l1 = [], l2 = [0] 输出：[0]

• 解法一：迭代法

解题思路

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode head;
        if (l1.val <= l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        ListNode listNode = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                listNode.next = l1;
                l1 = l1.next;
            } else {
                listNode.next = l2;
                l2 = l2.next;
            }
            listNode = listNode.next;
        }
        listNode.next = l1 == null ? l2 : l1;

        return head;
    }

• 解法二：递归法

解题思路

public ListNode mergeTwoList2(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    } else if (l2 == null) {
        return l1;
    } else {
        if (l1.val < l2.val) {
            l1.next = mergeTwoList2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoList2(l1, l2.next);
            return l2;
        }
    }
}

24. 两两交换链表中的节点

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

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

示例 1：

输入：head = [1,2,3,4] 输出：[2,1,4,3] 示例 2：

输入：head = [] 输出：[] 示例 3：

输入：head = [1] 输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100

进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）

解题思路

    // 解法一
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = first.next;
        ListNode temp = second.next;
        head = second;
        while (temp != null && temp.next != null) {
            first.next = temp.next;
            second.next = first;
            first = temp;
            second = first.next;
            temp = second.next;
        }
        first.next = second.next;
        second.next = first;
        return head;
    }
    // 解法二
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs2(newHead.next);
        newHead.next = head;
        return newHead;
    }

61. 旋转链表

解题思路一：让链表成环，然后从head遍历查找，从第k个位置个位置断开。

解题思路二：使用双指针，慢指针指向head，快指针指向k第个节点，然后两个指针指针同时移动，直到快指针的next为null，将慢指针next置为null，将快指针next指向head。

解题思路

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode listNode = head;
        int size = 1;
        // 遍历查找最后一个节点
        while (listNode.next != null) {
            listNode = listNode.next;
            size++;
        }
        k = k % size;
        if (k == 0) {
            // 如果移动距离为0，则直接返回head
            return head;
        }
        // 将尾结点指向头结点，构成一个链表环
        listNode.next = head;
        ListNode newHead;
        // 根据k查找断开位置
        for (int i = 0; i < size - k - 1; i++) {
            head = head.next;
        }
        // 头结点
        newHead = head.next;
        // 尾结点指向null
        head.next = null;
        return newHead;
    }

86. 分隔链表

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

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

输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5] 示例 2：

输入：head = [2,1], x = 2 输出：[1,2]

解题思路

public static ListNode partition(ListNode head, int x) {
    // 存储小于x的节点
    ListNode startList = new ListNode();
    // 存储大于等于x的节点
    ListNode endList = new ListNode();
    // 指向preList的尾结点
    ListNode startListTail = startList;
    // 指向endList的尾结点
    ListNode endListTail = endList;
    // 遍历链表
    while (head != null) {
        // 小于x的链表放入startList链表中
        if (head.val < x) {
            startListTail.next = head;
            startListTail = startListTail.next;
        } else {
            // 大于等于x的节点放入endList中
            endListTail.next = head;
            endListTail = endListTail.next;
        }
        head = head.next;
    }
    startListTail.next = null;
    endListTail.next = null;
    if (startList.next != null) {
        startListTail.next = endList.next;
        return startList.next;
    } else {
        return endList.next;
    }
}

141. 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。

• 解法一：双指针

解题思路

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

• 解法二：使用HashSet

解题思路

public boolean hasCycle2(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    HashSet<ListNode> hashSet = new HashSet<>();
    hashSet.add(head);
    while (head != null) {
        head = head.next;
        if (hashSet.contains(head)) {
            return true;
        }
        hashSet.add(head);
    }
    return false;
}

160. 相交链表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode node1 = headA ,node2 = headB;
    while(node1 != node2) {
        if(node1 != null) {
            node1 = node1.next;
        } else {
            node1 = headB;
        }

        if(node2 != null) {
            node2 = node2.next;
        } else {
            node2 = headA;
        }
    }
    return node1;
}

面试题 02.02. 返回倒数第 k 个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2 输出： 4 说明：

给定的 k 保证是有效的。

• 解法一：使用栈的先进先出特性

解题思路

public int kthToLast(ListNode head, int k) {
    Stack<ListNode> stackNode = new Stack<>();
    while (head != null) {
        stackNode.push(head);
        head = head.next;
    }
    for (int i = 0; i < k - 1; i++) {
        stackNode.pop();
    }
    return stackNode.pop().val;
}

• 解法二：遍历链表或得size,然后再找出倒数第k个元素

解题思路

public int kthToLast2(ListNode head, int k) {
    int size = getListSize(head);
    for (int i = 0; i < size - k; i++) {
        head = head.next;
    }
    return head.val;
}

• 解法三：双指针

解题思路

public int kthToLast3(ListNode head, int k) {
    ListNode listNode1 = head;
    ListNode listNode2 = head;
    for (int i = 0; i < k; i++) {
        listNode1 = listNode1.next;
    }
    while (listNode1 != null && listNode1.next != null) {
        listNode1 = listNode1.next;
        listNode2 = listNode2.next;
    }
    return listNode2.val;
}

private int getListSize(ListNode head) {
    int size = 0;
    while (head.next != null) {
        head = head.next;
        size++;
    }
    return ++size;
}

面试题 02.08. 环路检测

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。

• 解法一：使用HashSet存储Node,对比node是否在HashSet中存在

解题思路

public ListNode detectCycle(ListNode head) {
    HashSet<ListNode> hashSet = new HashSet<>();
    while (head != null) {
        if (hashSet.contains(head)) {
            return head;
        } else {
            hashSet.add(head);
            head = head.next;
        }
    }
    return null;
}

• 解法二：快慢指针，慢指针一次走一步，快指针一次走两步。

解题思路

public ListNode detectCycle2(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    ListNode listNode1 = head;
    ListNode listNode2 = head;
    while (listNode1.next != null && listNode2 != null && listNode2.next != null) {
        listNode1 = listNode1.next;
        listNode2 = listNode2.next.next;
        if (listNode1 == listNode2) {
            ListNode ptr = head;
            while (ptr != listNode1) {
                ptr = ptr.next;
                listNode1 = listNode1.next;
            }
            return ptr;
        }
    }
    return null;
}

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

1. 链表中节点数目在范围[1, 105] 内

2. 0 <= Node.val <= 9

• 解法一：复制链表，双指针校验

解题思路

public boolean isPalindrome(ListNode head) {
    if (head == null) {
        return false;
    }
    if (head.next == null) {
        return true;
    }
    List<Integer> list = new ArrayList<>();
    while (head != null) {
        list.add(head.val);
        head = head.next;
    }

    int left = 0, right = list.size() - 1;
    while (left < right) {
        if (!list.get(left).equals(list.get(right))) {
            return false;
        } else {
            left++;
            right--;
        }
    }
    return true;
}

• 解法二：将后半段链表反转，跟前半段对比

解题思路

public boolean isPalindrome2(ListNode head) {
    if (head == null) {
        return false;
    }
    if (head.next == null) {
        return true;
    }

    int size = 0;
    ListNode node = head;
    while (node != null) {
        node = node.next;
        size++;
    }

    int halfStart = size % 2 == 0 ? size / 2 : size / 2 + 1;
    int i = 0;
    ListNode halfNode = head;
    while (i < halfStart) {
        halfNode = halfNode.next;
        i++;
    }
    ListNode reverseNode = reverseNode(halfNode);

    while (reverseNode != null) {
        if (head.val != reverseNode.val) {
            return false;
        }
        head = head.next;
        reverseNode = reverseNode.next;
    }
    return true;
}

private ListNode reverseNode(ListNode node) {
    if (node == null || node.next == null) {
        return node;
    }
    ListNode lastNode = reverseNode(node.next);
    node.next.next = node;
    node.next = null;
    return lastNode;
}

237. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例 1：

输入：head = [4,5,1,9], node = 5 输出：[4,1,9] 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2：

输入：head = [4,5,1,9], node = 1 输出：[4,5,9] 解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

解题思路

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

445. 两数相加 II

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

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

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7] 示例2：

输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7] 示例3：

输入：l1 = [0], l2 = [0] 输出：[0]

解题思路

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Stack<ListNode> stack1 = new Stack<>();
    Stack<ListNode> stack2 = new Stack<>();
    while (l1 != null) {
        stack1.push(l1);
        l1 = l1.next;
    }
    while (l2 != null) {
        stack2.push(l2);
        l2 = l2.next;
    }
    int n = 0;
    ListNode head = null;
    while (!stack1.isEmpty() || !stack2.isEmpty()) {
        int sum = n;
        ListNode node = null;
        if (!stack1.isEmpty()) {
            node = stack1.pop();
            sum += node.val;
        }
        if (!stack2.isEmpty()) {
            node = stack2.pop();
            sum += node.val;
        }
        node.val = sum % 10;
        node.next = head;
        head = node;
        n = sum / 10;
    }
    if (n != 0) {
        ListNode node = new ListNode(n);
        node.next = head;
        return node;
    }
    return head;
}

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2] 输出：[2,3,1]

public int[] reversePrint(ListNode head) {
    ListNode node = head;
    Stack<Integer> stack = new Stack<>();
    while (node != null) {
        stack.push(node.val);
        node = node.next;
    }
    int[] result = new int[stack.size()];
    int i = 0;
    while (stack.iterator().hasNext()) {
        result[i++]= stack.pop();
    }
    return result;
}

剑指 Offer 18. 删除链表的节点

public ListNode deleteNode(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    if (head.val == val) {
        return head.next;
    }
    ListNode preNode = head;
    ListNode node = head.next;

    while (node != null) {
        if (node.val == val) {
            preNode.next = node.next;
            break;
        }
        preNode = preNode.next;
        node = node.next;
    }
    return head;
}

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

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

返回链表 4->5.

public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode listNode1 = head;
    ListNode listNode2 = head;
    for (int i = 0; i < k - 1; i++) {
        listNode1 = listNode1.next;
    }
    while (listNode1 != null && listNode1.next != null) {
        listNode1 = listNode1.next;
        listNode2 = listNode2.next;
    }
    return listNode2;
}

剑指 Offer 35. 复杂链表的复制 同 LeetCode 138. 复制带随机指针的链表

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2：

输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]] 示例 3：

输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]] 示例 4：

输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000 Node.random 为空（null）或指向链表中的节点。 节点数目不超过 1000 。

解题思路

将链表的每个结点都进行复制，并且将复制后的链表插入到该结点的下一个结点，新复制的链表的random与被复制的链表的random指向同一个结点。然后把复制的所有节点进行拆分，拆分时需要将所有复制的链表的random指向它的下一个节点。拆分完成后构成的新节点即复制出来的链表。

public static Node copyRandomList(Node head) {
    if (head == null) return null;
    Node n = head;
    while (n != null) {
        Node nextNode = n.next;
        Node node = new Node(n.val);
        node.random = n.random;
        node.next = n.next;
        n.next = node;
        n = nextNode;
    }

    Node node = head;
    int i = 0;
    while (node != null) {
        if (i++ % 2 == 1 && node.random != null) {
            node.random = node.random.next;
        }
        node = node.next;
    }

    // 新链表的头结点
    Node newHead = head.next;
    Node nextNode = newHead;
    while (nextNode.next != null) {
        head.next = head.next.next;
        head = head.next;
        nextNode.next = nextNode.next.next;
        nextNode = nextNode.next;
    }
    head.next = null;
    return newHead;
}

链表反转相关题

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 示例 2：

输入：head = [1,2] 输出：[2,1] 示例 3：

输入：head = [] 输出：[]

提示：

链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

• 解法一：迭代法

解题思路

public static ListNode reverseLink(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p1 = head;
    ListNode p2 = p1.next;
    ListNode p3;
    while (p2 != null) {
        p3 = p2.next;
        p2.next = p1;
        p1 = p2;
        p2 = p3;
    }
    head.next = null;
    return p1;
}

• 解法二：递归法

解题思路

递归的递流程直接找到递归的最后一个节点，最后一个节点的next为null,返回自身，然后开始递归的归流程递归的归流程，从最后一个节点向上回溯，将最后一个节点的next指向倒数第二个节点，倒数第二个节点的next指向null，以此回溯到第一个节点完成链表的反转。

public static ListNode reverseLink2(ListNode head) {
    // head == null这个条件一定要判断啊！！！！
    if (head == null || head.next == null) {
        return head;
    }
    // 返回最后一个节点
    ListNode lastNode = reverseLink2(head.next);
    head.next.next = head;
    head.next = null;
    return lastNode;
}

206 反转链表 扩展

解题思路

public static ListNode cursor;

public static ListNode reverseLink(ListNode head, int n) {
    if (n == 1) {
        cursor = head.next;
        return head;
    }
    ListNode lastNode = reverseLink(head.next, n - 1);
    head.next.next = head;
    head.next = cursor;
    return lastNode;
}

92. 反转链表 II

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

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5] 示例 2：

输入：head = [5], left = 1, right = 1 输出：[5]

提示：

链表中节点数目为 n 1 <= n <= 500 -500 <= Node.val <= 500 1 <= left <= right <= n

解题思路

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || head.next == null) {
    return head;
    }
    return reverse(head, left, right);
    }

private ListNode reverse(ListNode head, int left, int right) {
    if (left == 1) {
    return LeetCode92$.reverseLink(head, right);
    }
    head.next = reverse(head.next, left - 1, right - 1);
    return head;
    }