链表

Jing1042025/7/21大约 9 分钟

链表

第七个专题

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

思路一：将第一个链表的每个节点存入set中，然后遍历第二个链表的每一个节点，查看是否存在于set中，第一个存在的便是答案，如果不存在返回空（哈希思想）

/**
 * 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) {
        Set<ListNode> st = new HashSet<>();
        ListNode temp = headA;
        while(temp != null){
            st.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while(temp !=null){
            if(st.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;

        
    }
}

思路二：双指针，两个链表中节点相互比较，比较完成后同时转至下一节点，如果某个链表遍历完了，也就是遍历到null了，就跳转至另一个列表的头节点，以此往复总会有某一刻遍历到相交的节点，如果不相交，也总会有一刻遍历到null，只要两个节点相同就返回该节点

情况一：两个链表相交
链表 headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点，链表 headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，则有 a+c=m，b+c=n。
如果 a=b，则两个指针会同时到达两个链表相交的节点，此时返回相交的节点；
如果 a!=b，则指针 pA 会遍历完链表 headA，指针 pB 会遍历完链表 headB，两个指针不会同时到达链表的尾节点，然后指针 pA 移到链表 headB 的头节点，指针 pB 移到链表 headA 的头节点，然后两个指针继续移动，在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a 次之后，两个指针会同时到达两个链表相交的节点，该节点也是两个指针第一次同时指向的节点，此时返回相交的节点。
情况二：两个链表不相交
链表 headA 和 headB 的长度分别是 m 和 n。考虑当 m=n 和 m!=n 时，两个指针分别会如何移动：

如果 m=n，则两个指针会同时到达两个链表的尾节点，然后同时变成空值 null，此时返回 null；
如果 m!=n，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，在指针 pA 移动了 m+n 次、指针 pB 移动了 n+m 次之后，两个指针会同时变成空值 null，此时返回 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) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode lnA = headA;
        ListNode lnB = headB;
        while(lnA != lnB){
            lnA = lnA == null ? headB : lnA.next;
            lnB = lnB == null ? headA : lnB.next;
        }
        return lnA;
}
}

反转链表

反转链表
给你单链表的头节点 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 reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode temp = head;
        ListNode prev = null;
        while(temp != null){
            ListNode next = temp.next;//用next存储下一节点
            temp.next = prev;//将当前节点指向前一节点
            prev = temp;//前一节点后移
            temp = next;//当前节点后移
        }
        return prev;
    }
}

回文链表

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

思路一：用数组存链表的值，然后双指针比较

/**
 * 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 boolean isPalindrome(ListNode head) {
        ListNode temp = head;
        List<Integer> ls = new ArrayList<>();
        while(temp!=null){
            ls.add(temp.val);
            temp = temp.next;
        }
        int left = 0;
        int right = ls.size()-1;
        while(left<right){
            if(ls.get(left).equals(ls.get(right))){
                left++;
                right--;
            }else{
                return false;
            }
        } 
        return true;
    }
}

思路二：符合常规思维，将后半段做一个反转，然后从头比较两两是否相等，思路很简单，但是代码书写比较麻烦，这个的空间复杂度为O(1)

/**
 * 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 boolean isPalindrome(ListNode head) {
        if(head == null){
            return true;
        }
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverse(firstHalfEnd.next);
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        while(p1 != null &&p2 != null){
            if(p1.val != p2.val){
                reverse(secondHalfStart);
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;

        
    }
    private ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    private ListNode endOfFirstHalf(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null&&fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

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

思路一：使用哈希，将遍历到的节点用set存储起来，然后顺着链表节点遍历，如果后边某个节点在set中发现了，则说明出现了回环

/**
 * 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) {
        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;
    }
}

思路二：采用快慢指针，因为存在回环，所以两个指针终会碰到，如果碰到null则说明无回环，则返回false

/**
 * 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) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast.next == null || fast.next.next == null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
           
        }
        return true;
}
}

合并两个有序链表

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

思路一：递归，因为返回值为合并后的头节点，所以两个头节点比较后，递归调用较小值的next和较大值并作为较小值的新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 list1, ListNode list2) {
        //前置条件，不仅仅说明一个初始一个链表为空，答案肯定是另一个链表；也说明一个链表遍历结束，直接把另一个链表剩余节点直接连接上
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }else if(list1.val < list2.val){
            //递归调用
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list2.next,list1);
            return list2;
        }
    }
}

递归其实按照常规思维并不容易想到，更容易想到的应该是两两比较，再做节点连接，实际上，这种常规的迭代思维空间复杂度更低

思路二：常规迭代

/**
 * 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 list1, ListNode list2) {
        //先做了空对象判断
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }
        //对结果头节点做了初始化
        ListNode result = list1.val < list2.val ? list1 : list2;
        if(list1.val < list2.val){
            list1 = list1.next;
        }else{
            list2 = list2.next;
        }
        //使用prev临时记录当前节点
        ListNode prev = result;
        
        while(list1 != null && list2 != null){
        if(list1.val < list2.val){
            prev.next = list1;
            prev = list1;
            list1 = list1.next;

        }else{
            prev.next = list2;
            prev = list2;
            list2 = list2.next;
        }
        }
        //当一个链表到null时，另一个可能没有遍历完，直接加到末尾
        prev.next = list1 == null? list2:list1;
        return result;
    }
}
//这个符合常规逻辑，但是开始有些繁琐，因为我们过于着急的先去比较两个头节点，逻辑有些混乱，官方题解使用一个前置最小节点解决了这个问题

官方迭代题解：

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;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

链表

链表

相交链表

反转链表

回文链表

环形链表

合并两个有序链表