Leetcode算法系列二(链表)

1.8道经典链表常考题目

例1-a:反转链表
例1-b:反转链表2
例2:链表求交点
例3:链表求环
例4:链表划分
例5:复杂链表的复制
例6-a:2个排序链表归并
例6-b:K个排序链表归并

206.反转链表

反转一个单链表。

示例:

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

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead=null;
        while(head!=null){
            ListNode node=head.next;
            head.next=newHead;
            newHead=head;
            head=node;
        }

        return newHead;
    }
}

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dumy=new ListNode(-1);
        dumy.next=head;

        //移动m-1个位置
        ListNode pre=dumy;
        for(int i=1;i<m;i++){
            pre=pre.next;
        }
        //pre.next=head;
        head=pre.next;

        for(int i=m;i<n;i++){
            ListNode node=head.next;
            head.next=node.next;
            node.next=pre.next;
            pre.next=node;
        }

        return dumy.next;
    }
}

160. 相交链表

编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表:
在节点 c1 开始相交。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。

注意:
如果两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int n1=0,n2=0;
        n1=getLength(headA);
        n2=getLength(headB);
        if(n1>n2){
            headA=forwardLongList(n1,n2,headA);
        }else{
            headB=forwardLongList(n2,n1,headB);
        }

        while(headA!=null){
            if(headA==headB){
                return headA;
            }
            headA=headA.next;
            headB=headB.next;
        }

        return null;
    }

    public int getLength(ListNode head){
        int length=0;
        while(head!=null){
            length++;
            head=head.next;
        }
        return length;
    }

    public ListNode forwardLongList(int longLen,int shortLen,ListNode head){
        int changeLen=longLen-shortLen;
        for(int i=0;i<changeLen;i++){
           head=head.next;
        }

        return head;
    }

}

142. 环形链表 II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。
说明:不允许修改给定的链表。

进阶:
你是否可以使用 O(1) 空间解决此题?

示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        ListNode meet=null;//快慢指针相遇的位置

        while (fast!=null){
            fast=fast.next;
            slow=slow.next;

            if(fast==null){
                return null;
            }
            fast=fast.next;

            if(fast==slow){
                meet=fast;
                break;
            }
        }

        if(fast==null){
            return null;
        }

        while(meet!=null&&head!=null){
            if(meet==head){
                return head;
            }
            meet=meet.next;
            head=head.next;
        }

        return null;
    }
}

86. 分隔链表

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode lessHead=new ListNode(0);
        ListNode moreHead=new ListNode(0);
        ListNode lessPointer=lessHead;
        ListNode morePointer=moreHead;

        while(head!=null){
            if(head.val<x){
                lessPointer.next=head;
                head=head.next;
                lessPointer=lessPointer.next;
                lessPointer.next=null;
            }else{
                morePointer.next=head;
                head=head.next;
                morePointer=morePointer.next;
                morePointer.next=null;
            }
        }

        lessPointer.next=moreHead.next;
        return lessHead.next;
    }
}

138. 复制带随机指针的链表

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val,random_index] 表示:
val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 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。

public class Solution {
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        HashMap<Node,Integer> oldTable=new HashMap<>();//旧链表的地址映射:地址-》索引
        ArrayList<Node> nowTable=new ArrayList<>();//新链表的地址映射:索引-》地址

        Node ptr=head;
        int i=0;
        while(ptr!=null){
            oldTable.put(ptr,i);
            nowTable.add(new Node(ptr.val));
            ptr=ptr.next;
            i++;
        }
        i=0;
        ptr=head;
        while(ptr!=null){
            if(ptr.next==null){
                nowTable.get(i).next=null;
            }else{
                nowTable.get(i).next=nowTable.get(i+1);
            }
            if(ptr.random!=null){
            int id=oldTable.get(ptr.random);
            nowTable.get(i).random=nowTable.get(id);
            }
            ptr=ptr.next;
            i++;
        }

        return nowTable.get(0);
    }

}

21. 合并两个有序链表

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

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

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head=new ListNode(0);//头节点
        ListNode pre=head;

        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                pre.next=l1;
                l1=l1.next;
            }else{
                pre.next=l2;
                l2=l2.next;
            }
            pre=pre.next;
        }
        
        if(l1!=null){
            pre.next=l1;
        }
        if(l2!=null){
            pre.next=l2;
        }
        
        return head.next;
    }
}

23. 合并K个升序链表

给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2:
输入:lists = []
输出:[]
示例 3:
输入:lists = [[]]
输出:[]

提示:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0){
            return null;
        }else if(lists.length==1){
            return lists[0];
        }else if(lists.length==2){
            return mergeTwoLists(lists[0],lists[1]);
        }

        int mid=(lists.length)/2;
        ListNode[] lists1=new ListNode[mid];
        ListNode[] lists2=new ListNode[lists.length-mid];
        int k=0;
        for(int i=0;i<mid;i++){
            lists1[i]=lists[k++];
        }
        for(int i=0;i<lists.length-mid;i++){
            lists2[i]=lists[k++];
        }
        ListNode l1=mergeKLists(lists1);
        ListNode l2=mergeKLists(lists2);
        return mergeTwoLists(l1,l2);
    }
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head=new ListNode(0);//头节点
        ListNode pre=head;

        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                pre.next=l1;
                l1=l1.next;
            }else{
                pre.next=l2;
                l2=l2.next;
            }
            pre=pre.next;
        }

        if(l1!=null){
            pre.next=l1;
        }
        if(l2!=null){
            pre.next=l2;
        }

        return head.next;
    }
}

版权声明:本文为weixin_44337475原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。