LeetCode 算法之链表

Question

1.两个链表的交点

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

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3
A 和 B 两个链表相交于 c1

思路： 双指针。 设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。 当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。 如果不存在交点，那么 a + b = b + a，以下实现代码中 l1 和 l2 会同时为 null，从而退出循环。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        while(l1 != l2){
            l1 = (l1 == null) ? headB : l1.next;
            l2 = (l2 == null) ? headA : l2.next;
        }
        return l1;
    }
}

2.链表反转

206.反转一个单链表。 思路： 头插法。 两个指针，一个指向前结点，一个指向当前结点。

class Solution {
    public ListNode reverseList(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，3，4，5。按照递归，当执行 reverseList（5）的时候返回了 5 这个节点，reverseList(4)中的 p 就是 5 这个节点，我们看看 reverseList（4）接下来执行完之后，5->next = 4, 4->next = null。这时候返回了 p 这个节点，也就是链表 5->4->null，接下来执行 reverseList（3），代码解析为 4->next = 3,3->next = null，这个时候 p 就变成了，5->4->3->null, reverseList(2), reverseList(1)依次类推，p 就是:5->4->3->2->1->null

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

3.归并两个有序的链表

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

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

4.从有序链表中删除重复节点

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

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

思路： 递归。

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

非递归。 三个指针，前一节点、当前节点、下一节点。 另需一个指针指向头节点用于返回。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode result = head;
        ListNode pre = head, cur = head.next;
        while(cur != null){
            ListNode next = cur.next;
            if(cur.val == pre.val){
                cur.next = null;
                pre.next = next;
                cur = next;
            }else{
                pre = cur;
                cur = next;
            }
        }
        return result;
    }
}

剑指 56.删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5 思路： 遇到下一个是重复节点则一直向前走直到不是重复节点。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null || pHead.next==null) return pHead;
        ListNode cur = pHead, next = cur.next;
        ListNode pre = new ListNode(-1);
        pre.next = pHead;
        ListNode result = pre;
        while(cur != null){
            next = cur.next;
            if(next == null) break;
            //不相等先判断
            if(cur.val != next.val){
                pre = cur;
                cur = next;
                continue;
            }
            //这里空判断应该先判断
            while(next != null && cur.val == next.val){
                next = next.next;
            }
            pre.next = next;
            cur = next;
        }
        return result.next;
    }
}

5.删除链表的倒数第 n 个节点

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

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

思路： 快慢指针，先让快指针走 n 个，慢指针与快指针保持这个间隔。

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        for(int i = 0; i < n; i++){
            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;
    }
}

6.交换链表中的相邻结点

24.给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

Given 1->2->3->4, you should return the list as 2->1->4->3.

思路： 需要四个指针，两个指向当前交换的节点，一个指向前节点，一个指向后节点。

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode pre = node;
        while(pre.next != null && pre.next.next != null){
            ListNode l1 = pre.next;
            ListNode l2 = l1.next;
            ListNode next = l2.next;
            pre.next = l2;
            l2.next = l1;
            l1.next = next;
            pre = l1;
        } 

        return node.next;
    }
}

7.链表求和

2.给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

---

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

445.给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都不会以零开头。 条件：不能修改输入链表

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

思路： 使用两个栈来储存链表中的数字。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> l1Stack = bulidStack(l1);
        Stack<Integer> l2Stack = bulidStack(l2);
        ListNode result = new ListNode(-1);
        int carry = 0;

        while( !l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0){
            int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
            int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
            int sum = x + y + carry;
            ListNode node = new ListNode(sum % 10);
            node.next = result.next;
            result.next = node;
            carry = sum / 10;
        }

        return result.next;
    }

    public Stack<Integer> bulidStack(ListNode l){
        Stack<Integer> result = new Stack<>();
        while(l != null){
            result.push(l.val);
            l = l.next;
        }
        return result;
    }
}

8.回文链表

234.请判断一个链表是否为回文链表。 思路：

1. 将链表转换为数组。
2. 使用双指针法。

    class Solution {
   
        public boolean isPalindrome(ListNode head) {
            if(head == null) return true;
    
            ArrayList<Integer> list = new ArrayList<>();
    
            while(head != null){
                list.add(head.val);
                head = head.next;
            }
    
            int left = 0;
            int right = list.size() - 1;
    
            while(left < right){
                if(!list.get(left).equals(list.get(right))){
                    return false;
                }
                left ++;
                right --;
            }
    
            return true;
        }
    }
   

9.分割链表

725.给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。 每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。 这 k 个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。 返回一个符合上述规则的链表的列表。

Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

思路： 设链表长度为 n，则前 n%k 的链表比后面长 1，即前 n%k 长为 n/k +1，后面为 n/k。

class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        int n = 0;
        ListNode count = root;
        while(count != null){
            n++;
            count = count.next;
        }

        int mod = n % k;
        int size = n / k;

        ListNode[] result = new ListNode[k];
        ListNode head = root;
        for(int i = 0; head != null && i < k; i++){
            result[i] = head;
            int curSize = size + (mod -- >0 ? 1 : 0);
            for(int j = 0; j < curSize - 1; j++){
                head = head.next;
            }
            ListNode next = head.next;
            head.next = null;
            head = next;
        }

        return result;
    }
}

10.链表元素按奇偶聚集

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

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

思路： 需三个指针 使用两个指针，将当前链表按奇偶分成两个链表，另需要一个指针，来存偶链表的头结点，以便将其接入到奇链表的尾部。

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null) return null;

        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while(even != null && even.next != null){
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }

        odd.next = evenHead;
        return head;
    }
}

剑指 25.复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针 random 指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 思路： 将链表存入 map 中，以便之后寻找映射关系。

import java.util.HashMap;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null) return null;
        RandomListNode head1 = pHead; //记录 pHead 的头节点
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        while(pHead != null){
            map.put(pHead, new RandomListNode(pHead.label));
            pHead = pHead.next;
        }
        RandomListNode result = new RandomListNode(head1.label);
        RandomListNode head2 = result;//记录 result 的头节点
        while(head1 != null){
            result.next = map.get(head1.next);
            result.random = map.get(head1.random);
            result = result.next;
            head1 = head1.next;
        }
        return head2;
    }
}

剑指 46.圆圈中最后剩下的数

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF 作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数 m,让编号为 0 的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续 0...m-1 报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版（名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从 0 到 n-1) 如果没有小朋友，请返回-1 思路： 使用 List 模拟，使用一个指针。

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n == 0 || m == 0) return -1;
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 0; i < n; i++) list.add(i);
        int cur = -1;
        while(list.size()>1){
            for(int i = 0; i < m; i++){
                cur++;
                if(cur == list.size()) cur = 0;
            }
            list.remove(cur);
            //删除节点时，cur 会指向下一个节点，因此需要减 1。
            cur--;
        }
        return list.get(0);
    }
}