链表排序
# 206. 反转链表 (opens new window)
方法一：模拟
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur!=null){
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
方法二：递归
后序
class Solution { public ListNode reverseList(ListNode head) { if(head==null || head.next==null) return head; ListNode tail = reverseList(head.next); head.next.next = head; head.next = null; return tail; } }1
2
3
4
5
6
7
8
9前序
class Solution { public ListNode reverseList(ListNode head) { return dfs(null,head); } ListNode dfs(ListNode pre,ListNode cur){ if(cur==null) return pre; ListNode nxt = cur.next; cur.next = pre; return dfs(cur,nxt); } }1
2
3
4
5
6
7
8
9
10
11
# 160. 相交链表 (opens new window)
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while(p != q){
if(p!=null) p=p.next;
else p=headB;
if(q!=null) q=q.next;
else q=headA;
}
return p;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 143. 重排链表 (opens new window)
class Solution {
public void reorderList(ListNode head) {
ListNode mid = getMid(head);
ListNode head2 = reverse(mid);
while(head2.next!=null){
ListNode nxt = head.next;
ListNode nxt2 = head2.next;
head.next = head2;
head2.next = nxt;
// 步进
head = nxt;
head2 = nxt2;
}
}
ListNode getMid(ListNode head){
ListNode slow = head,fast = head;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
ListNode reverse(ListNode head){
if(head==null || head.next==null)
return head;
ListNode tail = reverse(head.next);
head.next.next = head;
head.next = null;
return tail;
}
}
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
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
# 快慢指针
# 876. 链表的中间结点 (opens new window)
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow=head,fast=head;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 141. 环形链表 (opens new window)
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head,fast = head;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast)return true;
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 142. 环形链表 II (opens new window)
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head,slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow)break;
}
if(fast==null||fast.next==null)return null;
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 234. 回文链表 (opens new window)
方法一：模拟
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head,slow = head;
ListNode p = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
if(fast!=null) slow = slow.next;
ListNode rightHead = reverse(slow);
while(rightHead!=null){
if(p.val != rightHead.val){
return false;
}
p = p.next;
rightHead = rightHead.next;
}
return true;
}
ListNode reverse(ListNode head){
if(head==null || head.next==null){
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
}
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
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
方法二：递归
class Solution {
ListNode p;
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
if(p == null) p = head;
boolean res = isPalindrome(head.next) && p.val==head.val;
p = p.next;
return res;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 虚拟头节点
# 2. 两数相加 (opens new window)
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
int carry = 0;
while(l1!=null || l2!=null){
int x = (l1==null?0:l1.val);
int y = (l2==null?0:l2.val);
int sum = x+y+carry;
carry = sum/10;
sum %= 10;
p.next = new ListNode(sum);
p = p.next;
if(l1!=null) l1=l1.next;
if(l2!=null) l2=l2.next;
}
if(carry==1){
p.next = new ListNode(1);
}
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 19. 删除链表的倒数第 N 个结点 (opens new window)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1,head);
ListNode node = findNthFromEnd(dummy,n+1);
node.next = node.next.next;
return dummy.next;
}
ListNode findNthFromEnd(ListNode p,int n){
ListNode p1=p,p2=p;
for(int i=0;i<n;i++){
p1 = p1.next;
}
while(p1!=null){
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 24. 两两交换链表中的节点 (opens new window)
方法一：模拟
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1,head);
ListNode p = dummy;
while(p.next!=null && p.next.next!=null){
ListNode tmp = head.next.next;
p.next = head.next;
head.next.next = head;
head.next = tmp;
//步进
p = head;
head = head.next;
}
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
方法二：递归
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode p1 = head;
ListNode p2 = head.next;
ListNode p3 = head.next.next;
p2.next = p1;
p1.next = swapPairs(p3);
return p2;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 24. 两两交换链表中的节点 (opens new window)
方法一：模拟
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1,head);
ListNode p = dummy;
while(p.next!=null&&p.next.next!=null){
ListNode tmp = head.next.next;
p.next = head.next;
head.next.next = head;
head.next = tmp;
//步进
p = head;
head = head.next;
}
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
方法二：递归
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode p1=head;
ListNode p2=head.next;
ListNode p3=head.next.next;
p2.next = p1;
p1.next = swapPairs(p3);
return p2;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 25. K 个一组翻转链表 (opens new window)
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int n = 0;
for(ListNode cur=head;cur!=null;cur=cur.next){
n++;
}
ListNode dummy = new ListNode(0,head);
ListNode p0 = dummy;
ListNode pre = null,cur = head;
for(;n>=k;n-=k){
for(int i=0;i<k;i++){
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
ListNode nxtdummy = p0.next;
p0.next.next = cur;
p0.next = pre;
p0 = nxtdummy;
}
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24