链表

链表

Jason Lv3

142. 环形链表 II

快慢指针 相遇时 相差的距离为环的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast,slow;
fast = slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast) break;
}
if(fast == null || fast.next == null) return null;
slow = head;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}

images

21. 合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head= new ListNode(0),cur = head;
while(list1!=null && list2!=null){ //注意不是list.next
if(list1.val<=list2.val){
cur.next=list1;
list1 = list1.next;
}
else{
cur.next=list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1!=null?list1:list2; //过于优雅
return head.next;
}
}

什么时候需要用虚拟头结点?我这里总结下:当你需要创造一条新链表的时候,可以使用虚拟头结点简化边界情况的处理。

比如说,让你把两条有序链表合并成一条新的有序链表,是不是要创造一条新链表?再比你想把一条链表分解成两条链表,是不是也在创造新链表?这些情况都可以使用虚拟头结点简化边界情况的处理。

86. 分隔链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode p = head;
ListNode head1=new ListNode(-1),cur1 = head1;
ListNode head2=new ListNode(-1),cur2 = head2;

while(p!=null){
if(p.val>=x){
cur2.next = p;
cur2 = cur2.next;
}
else{
cur1.next = p;
cur1 = cur1.next;
}
ListNode temp = p.next;
p.next = null;
p=temp;
}

cur1.next = head2.next;
return head1.next;
}
}

注意:断开原list 如果不断开原链表中的每个节点的 next 指针,那么就会出错,因为结果链表中会包含一个环。
总的来说,如果需要把原链表的节点接到新链表上,而不是 new 新节点来组成新链表的话,那么断开节点和原链表之间的链接可能是必要的

23. 合并K个升序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {                                    
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0) return null;
PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->(a.val-b.val)); //大小和排序规则
ListNode dump = new ListNode(-1),p=dump;
for(ListNode head:lists){
if(head!=null){
pq.add(head);
}
}

while(!pq.isEmpty()){
ListNode temp = pq.poll();
p.next = temp;
if(temp.next!=null) pq.add(temp.next);
p=p.next;
}

return dump.next;

}
}

19. 删除链表的倒数第N个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast=head;
ListNode slow=head;
for(int i=0;i<n;i++){
fast=fast.next;
}
if(fast==null) return head.next; //删头结点
while(fast.next!=null){ //因为null无next 所以会报错!
fast = fast.next;
slow = slow.next;
}
slow.next=slow.next.next;
return head;
}
}

考虑头结点 若删的是头结点 则null.next报错

876. 链表的中间结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public ListNode middleNode(ListNode head) {
ListNode p = head;
ListNode q = head;
double count=0;
while(p.next!=null){
count++;
p=p.next;
}
count = Math.ceil(count/2);
while(count>0){
q=q.next;
count--;
}
return q;
}
}

160. 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while(p1!=p2){
if(p1==null) p1=headB;
else p1=p1.next;
if(p2==null) p2=headA;
else p2=p2.next;
}
return p1;
}
}
  • Title: 链表
  • Author: Jason
  • Created at : 2023-09-12 10:58:41
  • Updated at : 2023-09-12 18:26:25
  • Link: https://xxxijason1201.github.io/2023/09/12/LeetCode/链表/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments