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