链表题(持续更新)

链表类ListNode定义

import java.util.Arrays;

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }

    public static int[] toArray(ListNode head){
        int[] arr = {};
        while (head != null){
            arr = Arrays.copyOf(arr, arr.length+1);
            arr[arr.length-1] = head.val;
            head = head.next;
        }
        return arr;
    }

    public static ListNode fromArray(int[] arr){
        if (arr.length == 0) return null;

        ListNode ll = new ListNode(arr[0]);
        ListNode head = ll;
        for (int i = 1; i < arr.length; i++){
            ll.next = new ListNode(arr[i]);
            ll = ll.next;
        }
        return head;
    }

}

提供了导入导出为数组的内置静态方法。

问题

反转链表

题目描述：输入一个链表，反转链表后，输出新链表的表头。

代码：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev, curr, next, result;
        prev = null;
        curr = head;
        result = curr;
        while (curr != null){
            next = curr.next;
            curr.next = prev;
            result = curr;
            prev = curr;
            curr = next;
        }
        return result;
    }
}

// 更简洁的
public static ListNode reverseList(ListNode head){
    ListNode prev, curr, next;
    prev = null; curr = head; 
    while(curr != null){
        next = curr.next;
        curr.next= prev; 
        prev = curr;
        curr = next;
    }
    return prev;
}

链表有环

题目描述：判断给定的链表中是否有环 扩展：你能给出空间复杂度\(O(1)\)的解法么？

解法: 快慢指针

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

合并有序列表

题目描述：将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的

解法: 类似归并排序的思路

import java.util.Arrays;

public class LL {
    public static ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // Initialize 
        ListNode last;
        if (l1.val <= l2.val) {
            last = l1;
            l1 = l1.next;
        } else {
            last = l2;
            l2 = l2.next;
        }
        ListNode result = last;

        while(l1 != null && l2 != null){
            // System.out.printf("l1.val {%d}, l2.val {%d}\n", l1.val, l2.val);
            if (l1.val <= l2.val){
                last.next = l1;
                l1 = l1.next;
            } else {
                last.next = l2;
                l2 = l2.next;
            }
            last = last.next;
        }
        while(l1 != null){
            // System.out.printf("l1.val {%d}\n", l1.val);
            last.next = l1;
            l1 = l1.next;
            last = last.next;
        }
        while(l2 != null){
            // System.out.printf("l2.val {%d}\n", l2.val);
            last.next = l2;
            l2 = l2.next;
            last = last.next;
        }
        return result;
    }

    public static void main(String[] args){
        int[] a1 = {1,2,3,3,3};
        int[] a2 = {2,3,4,5};

        ListNode l1 = ListNode.fromArray(a1);
        ListNode l2 = ListNode.fromArray(a2);
        ListNode merged = mergeTwoLists(l1, l2);
        System.out.println(Arrays.toString(ListNode.toArray(merged)));
    }
}

(9.7)删除链表的倒数第n个节点

题目描述：

• 给定一个链表，删除链表的倒数第n个节点并返回链表的头指针

• 例如， 给出的链表为:1->2->3->4->5, n= 2. 删除了链表的倒数第n个节点之后,链表变为1->2->3->5.

• 备注：题目保证n一定是有效的

• 请给出时间复杂度为 \(O(n)\) 的算法

public static ListNode removeNthFromEnd(ListNode head, int n) {
    // write code here
    ListNode prev, curr, next;
    int len = 0;
    curr = head;
    while (curr != null) {
        curr = curr.next;
        len++;
    }

    // 去除head
    if (n == len) {
        return head.next;
    }

    curr = head;
    for (int i = 0; i < len - n - 1; i++) {
        curr = curr.next;
    }
    prev = curr;
    curr = curr.next;
    next = curr.next;
    prev.next = next;
    return head;
}

(9.7)两个链表生成相加链表

题目描述：

• 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
• 给定两个这种链表，请生成代表两个整数相加值的结果链表。
• 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

分析：

用到了之前的反转链表，以及数组相加的策略（进位）。链表增加结点需要考虑初始化的情况。最重要的还是确定哪一步同步current和result两个链表。 讨论区反映java卡75%算例，超时。

import java.util.Arrays;

public class addInList0907 {
    public static ListNode addInList(ListNode head1, ListNode head2) {
        // write code here
        ListNode head1Rev = reverseList(head1);
        ListNode head2Rev = reverseList(head2);
        ListNode mergeRevCurr = null;
        ListNode mergeRev = mergeRevCurr;

        int cache = 0;
        int digit = 0;
        boolean init = true;

        while (head1Rev != null && head2Rev != null) {
            digit = head1Rev.val + head2Rev.val + cache;
            if (digit >= 10) {
                digit -= 10;
                cache = 1;
            } else {
                cache = 0;
            }
            ListNode currDigit = new ListNode(digit);

            if (init) {
                init = false;
                mergeRevCurr = currDigit; // 这一步同步
                mergeRev = mergeRevCurr;
                // System.out.println(Arrays.toString(ListNode.toArray(mergeRev)));
            } else {
                mergeRevCurr.next = currDigit;
                mergeRevCurr = mergeRevCurr.next;
            }
            head1Rev = head1Rev.next;
            head2Rev = head2Rev.next;

        }

        while (head1Rev != null) {
            digit = head1Rev.val + cache;
            if (digit >= 10) {
                digit -= 10;
                cache = 1;
            } else {
                cache = 0;
            }
            ListNode currDigit = new ListNode(digit);

            if (init)
                mergeRevCurr = currDigit;
            else {
                mergeRevCurr.next = currDigit;
                mergeRevCurr = mergeRevCurr.next;
            }
            head1Rev = head1Rev.next;
        }

        while (head2Rev != null) {
            digit = head2Rev.val + cache;
            if (digit >= 10) {
                digit -= 10;
                cache = 1;
            } else {
                cache = 0;
            }
            ListNode currDigit = new ListNode(digit);

            if (init)
                mergeRevCurr = currDigit;
            else {
                mergeRevCurr.next = currDigit;
                mergeRevCurr = mergeRevCurr.next;
            }
            head2Rev = head2Rev.next;
        }

        if (cache == 1) {
            // System.out.println(Arrays.toString(ListNode.toArray(mergeRev)));
            ListNode currDigit = new ListNode(1);
            mergeRevCurr.next = currDigit;
            mergeRevCurr = mergeRevCurr.next;
        }

        return reverseList(mergeRev);
    }

    public static ListNode reverseList(ListNode head) {
        ListNode prev, curr, next;
        prev = null;
        curr = head;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode l1 = ListNode.fromArray(new int[] { 5, 9, 7, 5, 7, 1, 2, 6, 4, 2, 7, 8, 9, 6, 1, 6, 6, 1, 1, 4, 2, 9,
                5, 5, 0, 4, 6, 3, 0, 4, 3, 5, 6, 7, 0, 5, 5, 4, 4, 0 });
        ListNode l2 = ListNode.fromArray(new int[] { 1, 3, 2, 5, 0, 6, 0, 2, 1, 4, 3, 9, 3, 0, 9, 9, 0, 3, 1, 6, 5, 7,
                8, 6, 2, 3, 8, 5, 0, 9, 7, 9, 4, 5, 9, 9, 4, 9, 3, 6 });
        // System.out.println(Arrays.toString(ListNode.toArray(reverseList(l1))));
        System.out.println(Arrays.toString(ListNode.toArray(addInList(l2, l1))));
    }
}

(9/14) 链表中环的入口节点

题目描述

• 对于一个给定的链表，返回环的入口节点，如果没有环，返回null

解题思路

• 首先用快慢指针判断是否存在环
• 如存在环，假设环前长度为 d , 环长度为 l , 相遇点在环入口后 s 处

\[ d+l+s = 2*(d+s) \] \[ d+s = l \]

• 快指针归零，再走 (l-s)
• 慢指针

\[ d+s+(l-s)=d+l \]

• 快指针

\[ l-s = d\]

• 二者在 d 处相遇

代码

public class NowCoder_DetectCycle {
    public static ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode ptr1 = head;
        ListNode ptr2 = head;
        ListNode meetpoint = null;
        while(ptr1 != null && ptr1.next != null){
            ptr1 = ptr1.next.next;
            ptr2 = ptr2.next;
            if (ptr2 == ptr1){
                meetpoint = ptr1;
                break;
            }
        }
        // 判断是否有环
        if (meetpoint == null) return null;
        // 快指针从头出发，慢指针接着走
        ptr1 = head;
        while(ptr1 != ptr2){
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr1;
    }

    public static void main(String[] args){
        ListNode l1 = ListNode.fromArray(new int[]{1,3,5,7,9});
        l1.next.next.next.next.next = l1.next.next;
        ListNode l2 = new ListNode(1);
        System.out.println(detectCycle(l2).val);
    }
}

(9/14) 两个链表的第一个公共节点

题目描述

• 输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

解题思路1——链表成环

• 两链表应该呈现出 “Y” 形。把第二个链表接到第一个链表尾巴上形成一个环，若存在公共节点，则必形成环。
• 如果保留 p1, 最后的节点 temp -> p2。用 detectCycle(p1) 找出节点 result。再将temp -> p2 断开。返回result。
• 代码如下

public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if(pHead1 == null || pHead2 == null) return null;

    ListNode curr = pHead1;
    while (curr.next != null) curr = curr.next;
    curr.next = pHead2;
    // 把两个链表接起来找第一个

    ListNode firstCommon = detectCycle(pHead1);
    // 断开两个链表
    curr.next = null;
    return firstCommon;
}

public static ListNode detectCycle(ListNode head) {
    if (head == null) return null;
    ListNode ptr1 = head;
    ListNode ptr2 = head;
    ListNode meetpoint = null;
    while(ptr1 != null && ptr1.next != null){
        ptr1 = ptr1.next.next;
        ptr2 = ptr2.next;
        if (ptr2 == ptr1){
            meetpoint = ptr1;
            break;
        }
    }
    if (meetpoint == null) return null;
    // 快指针从头出发，慢指针接着走
    ptr1 = head;
    while(ptr1 != ptr2){
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
    }
    return ptr1;
}

解题思路2

• 先遍历两链表，分别得出长度
• 较长者截取掉更长的部分，因为共同部分肯定比较短的链表更短
• 然后两链表同时向后遍历直到二者相同
• 代码如下

// 解法：截取长度并依次比较。复杂度O(m+n)
public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    ListNode p1 = pHead1;
    ListNode p2 = pHead2;
    int len1 = 0, len2 = 0;

    while (p1 != null){
        p1 = p1.next;
        len1++;
    }
    while (p2 != null){
        p2 = p2.next;
        len2++;
    }

    if (len1 >= len2){
        for(int i = 0; i < len1 - len2; i++){
            pHead1 = pHead1.next;
        }
    } else {
        for(int i = 0; i < len2 - len1; i++){
            pHead2 = pHead2.next;
        }
    }
    while (pHead1 != pHead2){
        pHead1 = pHead1.next;
        pHead2 = pHead2.next;
    }
    return pHead1;
}