链表选编
法一：递归
关键：如何确定后序reversed linked list的尾结点？
答案：由于是从后向前递归，head.next之后的指针被修改，但head的指针未被修改，head.next依然可以找到原链表中的后继，而此时它已经成为了reverse linked list的尾，将head添加到其后即可
1
2
3
4
5
6
7
8
9
10
11
12
| public ListNode reverseList(ListNode head) {
if(head==null){
return null;
}
if(head.next==null){
return head;
}
ListNode postHead=reverseList(head.next);
head.next.next=head;
head.next=null;
return postHead;
}
|
法二：迭代
1
2
3
4
5
6
7
8
9
10
11
| public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode p=head;
while(p!=null){
ListNode temp=p.next;
p.next=pre;
pre=p;
p=temp;
}
return pre;
}
|
法一：递归
1
2
3
4
5
6
7
8
9
10
| public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode next=head.next;
ListNode postHead=swapPairs(head.next.next);
next.next=head;
head.next=postHead;
return next;
}
|
法二：迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode dummyHead=new ListNode(-1,head);
ListNode pre=dummyHead;
while(pre.next!=null && pre.next.next!=null){
ListNode temp=head.next.next;
pre.next=head.next;
head.next.next=head;
head.next=temp;
pre=head;
head=temp;
}
return dummyHead.next;
}
|
法一：用HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class LeetCode142 {
public ListNode detectCycle(ListNode head) {
Set<ListNode> set=new HashSet<>();
while(head!=null){
if(set.contains(head)){
return head;
}
set.add(head);
head=head.next;
}
return null;
}
}
|
法二：双指针
https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E6%80%9D%E8%B7%AF
那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
1
| (x + y) * 2 = x + y + n (y + z)
|
两边消掉一个（x+y）: x + y = n (y + z)
因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
所以要求x ，将x单独放在左面：x = n (y + z) - y ,
再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public ListNode detectCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
ListNode meet=fast;
ListNode h=head;
while(meet!=h){
meet=meet.next;
h=h.next;
}
return h;
}
}
return null;
}
|
注意：最后要将最后一个结点的next置为null，否则会成环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public void reorderList(ListNode head) {
List<ListNode> nodes=new ArrayList<>();
ListNode right=head;
int r=0;
nodes.add(right);
while(right.next!=null){
right=right.next;
nodes.add(right);
r++;
}
ListNode dummy=new ListNode();
ListNode p=dummy;
ListNode left=head;
int l=0;
while(l<r){
left=nodes.get(l);
right=nodes.get(r);
p.next=left;
p=p.next;
l++;
p.next=right;
p=p.next;
r--;
}
if(l==r){
p.next=nodes.get(l);
p=p.next;
}
p.next=null;
}
|
2. Add Two Numbers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy=new ListNode();
ListNode pre=dummy;
int preVal=0;
while(l1!=null || l2!=null){
int curVal=preVal;
if(l1!=null){
curVal+=l1.val;
}
if(l2!=null){
curVal+=l2.val;
}
preVal=curVal/10;
curVal%=10;
ListNode cur=new ListNode(curVal);
pre.next=cur;
pre=pre.next;
if(l1!=null){
l1=l1.next;
}
if(l2!=null){
l2=l2.next;
}
}
if(preVal!=0){
ListNode cur=new ListNode(preVal);
pre.next=cur;
}
return dummy.next;
}
|
234. Palindrome Linked List
好题：
- reverse
- findMid(end of first half)
- 判断完毕注意还原
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| public boolean isPalindrome(ListNode head) {
ListNode endOfFirstHalf=endOfFirstHalf(head);
ListNode startofSecondHalf=endOfFirstHalf.next;
ListNode end=reverse(startofSecondHalf);
ListNode p1=head;
ListNode p2=end;
boolean res=true;
while(res && p2!=null){
if(p1.val!=p2.val){
res=false;
}
p1=p1.next;
p2=p2.next;
}
endOfFirstHalf.next=reverse(end);
return res;
}
ListNode reverse(ListNode head){
ListNode pre=null;
ListNode p=head;
ListNode next=null;
while(p!=null){
next=p.next;
p.next=pre;
pre=p;
p=next;
}
return pre;
}
ListNode endOfFirstHalf(ListNode head){
ListNode fast=head;
ListNode slow=head;
while(fast.next!=null && fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
|
237. Delete Node in a Linked List
骚！
1
2
3
4
5
6
| public void deleteNode(ListNode node) {
ListNode next=node.next;
node.val=next.val;
node.next=next.next;
next.next=null;
}
|
328. Odd Even Linked List
考虑点数的奇偶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public ListNode oddEvenList(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode head2=new ListNode();
ListNode p2=head2;
ListNode p=head;
ListNode pre=null;
ListNode next=null;
while(p!=null && p.next!=null){
next=p.next.next;
p2.next=p.next;
p2=p2.next;
p2.next=null;
p.next=next;
pre=p;
p=next;
}
if(p!=null){
p.next=head2.next;
}else{
pre.next=head2.next;
}
return head;
}
|
369. Plus One Linked List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public ListNode plusOne(ListNode head) {
Deque<ListNode> stack=new LinkedList<>();
ListNode p=head;
while(p.next!=null){
stack.push(p);
p=p.next;
}
p.val++;
boolean remain=false;
if(p.val>9){
p.val=0;
remain=true;
p=stack.isEmpty() ? null : stack.pop();
}
while(p!=null && remain){
if(p.val!=9){
p.val++;
remain=false;
break;
}else{
p.val=0;
p=stack.isEmpty() ? null : stack.pop();
}
}
if(p==null){
ListNode h=new ListNode(1);
h.next=head;
return h;
}else{
return head;
}
}
|
708. Insert into a Sorted Circular Linked List
法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| public Node insert(Node head, int insertVal) {
if(head==null){
Node h=new Node(insertVal);
h.next=h;
return h;
}
Node o=head;
head=findHead(o);
Node pre=head;
Node p=head.next;
Node node=new Node(insertVal);
boolean finished=false;
while(p!=head){
if(pre.val<=insertVal && p.val>=insertVal){
pre.next=node;
node.next=p;
finished=true;
break;
}
pre=p;
p=p.next;
}
if(!finished){
pre.next=node;
node.next=p;
}
return o;
}
Node findHead(Node node){
Set<Node> set=new HashSet<>();
Node p=node;
Node min=p;
while(!set.contains(p)){
if(min.val>p.val){
min=p;
}
set.add(p);
p=p.next;
}
return min;
}
|
法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public Node insert(Node head, int insertVal) {
Node r = new Node(insertVal,null);
if(head == null){
r.next = r;
return r;
}
Node n = head;
while(true){
if((insertVal >= n.val && insertVal <= n.next.val)
|| (n.next.val < n.val && (insertVal >= n.val || insertVal <= n.next.val))
|| n.next == head){
r.next = n.next;
n.next = r;
break;
}
n = n.next;
}
return head;
}
|
1019. Next Greater Node In Linked List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public int[] nextLargerNodes(ListNode head) {
Deque<int[]> stack=new LinkedList<>();
int n=0;
ListNode p=head;
while(p!=null){
p=p.next;
n++;
}
int[] res=new int[n];
p=head;
int i=0;
while(p!=null){
while(!stack.isEmpty() && stack.peek()[1]<p.val){
int[] arr=stack.pop();
res[arr[0]]=p.val;
}
stack.push(new int[]{0,p.val});
p=p.next;
i++;
}
return res;
}
|
2130. Maximum Twin Sum of a Linked List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public int pairSum(ListNode head) {
List<Integer> list=new ArrayList<>();
while(head!=null){
list.add(head.val);
head=head.next;
}
int n=list.size();
int max=0;
for(int i=0; i<n/2; i++){
max=Math.max(max,list.get(i)+list.get(n-i-1));
}
return max;
}
|
1721. Swapping Nodes in a Linked List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public ListNode swapNodes(ListNode head, int k) {
ListNode p=head;
int n=0;
while(p!=null){
n++;
p=p.next;
}
p=head;
ListNode a=null;
ListNode b=null;
for (int i = 0; i < n; i++) {
if(i==k-1){
a=p;
}
if(i==n-k){
b=p;
}
p=p.next;
}
int temp=a.val;
a.val=b.val;
b.val=temp;
return head;
}
|
2046. Sort Linked List Already Sorted Using Absolute Values
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| private class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public ListNode sortLinkedList(ListNode head) {
ListNode negHead=null;
ListNode negTail=null;
ListNode dummy=new ListNode();
dummy.next=head;
ListNode p=head;
ListNode pre=dummy;
while(p!=null){
if(p.val<0){
ListNode next=p.next;
pre.next=next;
p.next=null;
if(negHead==null){
negTail=p;
}else{
p.next=negHead;
}
negHead=p;
p=next;
}else{
pre=p;
p=p.next;
}
}
if(negTail!=null){
negTail.next=dummy.next;
return negHead;
}
return head;
}
|
445. Add Two Numbers II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<ListNode> stack1=new LinkedList<>();
Deque<ListNode> stack2=new LinkedList<>();
ListNode last=null;
int carry=0;
while(l1!=null){
stack1.push(l1);
l1=l1.next;
}
while(l2!=null){
stack2.push(l2);
l2=l2.next;
}
while(!stack1.isEmpty() && !stack2.isEmpty()){
ListNode a=stack1.pop();
ListNode b=stack2.pop();
int val=(a.val+b.val+carry)%10;
carry=(a.val+b.val+carry)/10;
ListNode node=new ListNode(val);
node.next=last;
last=node;
}
while(!stack1.isEmpty()){
ListNode a=stack1.pop();
int val=(a.val+carry)%10;
carry=(a.val+carry)/10;
ListNode node=new ListNode(val);
node.next=last;
last=node;
}
while(!stack2.isEmpty()){
ListNode b=stack2.pop();
int val=(b.val+carry)%10;
carry=(b.val+carry)/10;
ListNode node=new ListNode(val);
node.next=last;
last=node;
}
if(carry!=0){
ListNode node=new ListNode(1);
node.next=last;
last=node;
}
return last;
}
|