算法-链表

链表和问题

两个非空链表表示两个数,数字倒叙排列,比如 (2 -> 4 -> 3) + (5 -> 6 -> 4) 表示 342 + 465 = 807., 最后输出应该为7 -> 0 -> 8。

注意进位问题就好了。

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class AddTwoNumber_2 {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode h1 = l1, h2 = l2;
ListNode result = new ListNode(0);
ListNode cur;
int c = 0;
cur = result;
while (h1 != null || h2 != null || c == 1) {
int tmp;
if (h1 == null && h2 == null) {
tmp = c;
} else if (h1 == null) {
tmp = c + h2.val;
} else if (h2 == null) {
tmp = c + h1.val;
} else {
tmp = c + h1.val + h2.val;
}
cur.next = new ListNode(tmp % 10);
c = tmp / 10;
cur = cur.next;
if (h1 != null)
h1 = h1.next;
if (h2 != null)
h2 = h2.next;
}
return result.next;
}
}

和上题类似,只是数字存储为顺序存储,解决方法为引入栈和dummy头节点。

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
package leetcode.linkedList;
import java.util.Stack;
/**
* Created by cdx0312
* 2018/4/7
*/
public class AddTwoNumbersII_445 {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
ListNode cur1 = l1, cur2 = l2;
while (cur1 != null) {
stack1.push(cur1.val);
cur1 = cur1.next;
}
while (cur2 != null) {
stack2.push(cur2.val);
cur2 = cur2.next;
}
int c = 0;
ListNode result = new ListNode(0);
while (!stack1.isEmpty() || !stack2.isEmpty() || c == 1) {
int tmp = 0;
if (stack1.isEmpty() && stack2.isEmpty())
tmp = c;
else if (stack1.isEmpty())
tmp = c + stack2.pop();
else if (stack2.isEmpty())
tmp = c + stack1.pop();
else
tmp = stack1.pop() + stack2.pop() + c;
ListNode node = new ListNode(tmp % 10);
c = tmp / 10;
node.next = result.next;
result.next = node;
}
return result.next;
}
}

删除链表中的节点

由于给出的是要删除的节点,无法获取其上一个节点,因此将其下一个节点的值复制过来,删除其下一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class DeleteNodeInALinkedList_237 {
public void deleteNode(ListNode node) {
if (node == null)
return;
if (node.next == null) {
node = null;
return;
}
node.val = node.next.val;
node.next = node.next.next;
}
}

链表中删除一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class RemoveLinkedListElement_203 {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = head, pre = dummy;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = pre.next;
}
cur = cur.next;
}
return dummy.next;
}
}

删除链表中离end第N的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class RemoveNthNodeFromEndOfList_19 {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode l = dummy;
ListNode r =dummy;
for (int i = 0; i < n + 1; i++) {
r = r.next;
}
while (r != null) {
l = l. next;
r = r.next;
}
l.next = l.next.next;
return dummy.next;
}
}

链表排序问题

对一个链表进行插入排序

设置dummy头节点,然后找到当前节点需要插入的位置。

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class InsertionSortList_147 {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
if (cur.next != null && cur.next.val < cur.val) {
while (pre.next.val < cur.next.val)
pre = pre.next;
ListNode tmp = cur.next;
cur.next = cur.next.next;
tmp.next = pre.next;
pre.next = tmp;
pre = dummy;
} else {
cur = cur.next;
}
}
return dummy.next;
}
}

合并两个有序链表

百度二面遇到了,这个解法是设置dummy头节点,当时自己选择的是递归方法,比较好想。

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class MergeTwoSortedLists_21 {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode node1 = l1;
ListNode node2 = l2;
ListNode curr = dummy;
while (node1 != null || node2 != null) {
if (node1 == null) {
curr.next = node2;
break;
} else if (node2 == null) {
curr.next = node1;
break;
} else {
if (node1.val <= node2.val) {
curr.next = node1;
node1 = node1.next;
} else {
curr.next = node2;
node2 = node2.next;
}
curr = curr.next;
}
}
return dummy.next;
}
}

归并排序

快慢指针将链表分为两部分,对两部分进行继续拆分,然后返回其合并结果。复杂度为O(NlogN)。

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class SortList_148 {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fast = head, slow = head;
ListNode prev = null, left, right;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
left = sortList(head);
right = sortList(slow);
return mergeTwoList(left, right);
}
public ListNode mergeTwoList(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
if (l1 != null)
prev.next = l1;
if (l2 != null)
prev.next = l2;
return dummy.next;
}
}

链表调整问题

奇数前偶数后的问题

创建两个dummy节点,最后两个连接起来就可以了。

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class OddEvenLinkedList_328 {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode odd = new ListNode(0);
ListNode even = new ListNode(0);
ListNode lastOdd = odd;
ListNode lastEven = even;
ListNode cur = head;
int i = 1;
while (cur != null) {
if (i % 2 == 0) {
lastEven.next = cur;
lastEven = lastEven.next;
} else {
lastOdd.next = cur;
lastOdd = lastOdd.next;
}
cur = cur.next;
i++;
}
lastEven.next = null;
lastOdd.next = even.next;
return odd.next;
}
}

partion问题,将链表中小于target值的节点放在前面。解决思路还是两个dummy节点。

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
package leetcode.linkedList;
import java.util.List;
/**
* Created by cdx0312
* 2018/4/7
*/
public class PartitionList_86 {
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null)
return head;
ListNode smaller = new ListNode(0);
ListNode bigger = new ListNode(0);
ListNode lastSmall = smaller;
ListNode lastbig = bigger;
ListNode cur = head;
while (cur != null) {
if (cur.val < x){
lastSmall.next = cur;
lastSmall = lastSmall.next;
}
if (cur.val >= x) {
lastbig.next = cur;
lastbig = lastbig.next;
}
cur = cur.next;
}
lastbig.next = null;
lastSmall.next = bigger.next;
return smaller.next;
}
}

将链表 L: L0→L1→…→Ln-1→Ln 变为 L0→Ln→L1→Ln-1→L2→Ln-2→…解决思路,快慢指针加上链表反转。

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class RecordList_143 {
public void reorderList(ListNode head) {
if (head == null || head.next == null)
return;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow.next = reverseList(slow.next);
fast = slow.next;
ListNode node = head;
while (node != slow) {
slow.next = fast.next;
fast.next = node.next;
node.next = fast;
node = fast.next;
fast = slow.next;
}
}
private ListNode reverseList(ListNode head) {
if (head == null)
return head;
ListNode p = head.next;
head.next = null;
while (p != null) {
ListNode tmp = p;
p = p.next;
tmp.next = head;
head = tmp;
}
return head;
}
}

排序链表中删除重复节点,要求保留一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class RemoveDuplicatesFromSortedList {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode pre = head;
ListNode cur = head.next;
while (cur != null) {
if (cur.val == pre.val)
pre.next = cur.next;
else {
pre.next = cur;
pre = pre.next;
}
cur = cur.next;
}
return head;
}
}

排序链表中删除重复节点,要求删除所有重复的

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class RemoveDuplicatesFromSortedListII_82 {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy, cur = head;
boolean repeat = false;
while(cur.next != null){
if(cur.val == cur.next.val){
repeat = true;
cur = cur.next;
} else {
cur = cur.next;
if(!repeat){
pre = pre.next;
}
pre.next = cur;
repeat = false;
}
}
if(repeat) pre.next = null;
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package leetcode.linkedList;
import java.util.List;
/**
* Created by cdx0312
* 2018/4/7
*/
public class ReverseLinkedList_206 {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
/**
* 创建一个链表
* @param arr
* @param n
* @return
*/
public static ListNode createLinkedList(int arr[], int n) {
if (n == 0)
return null;
ListNode head = new ListNode(arr[0]);
ListNode curNode = head;
for (int i = 1; i < n; i++) {
curNode.next = new ListNode(arr[i]);
curNode = curNode.next;
}
return head;
}
public static void printLinkedList(ListNode head) {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " -> ");
cur = cur.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
int arr[] = {1, 2, 3, 4, 5};
int n = arr.length;
ListNode head = createLinkedList(arr, n);
printLinkedList(head);
head = new ReverseLinkedList_206().reverseList(head);
printLinkedList(head);
}
}

反转指定位置的链表,解决思路,添加dummy节点,找到位置即可。

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class ReverseLinkedListII_92 {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null)
return null;
ListNode newHead = new ListNode(0);
newHead.next = head;
ListNode pre= newHead;
for (int i = 0; i < m-1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
ListNode next = cur.next;
for (int j = 0; j < n-m; j++) {
cur.next = next.next;
next.next = pre.next;
pre.next = next;
next = cur.next;
}
return newHead.next;
}
}

以K个为一组来反转链表,添加dummy节点,K个节点处理一次,不足k个不处理

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class ReverseNodesInKGroup_25 {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
ListNode start = dummy;
dummy.next = head;
while (true) {
ListNode node = start, cur, n = node;
start = node.next;
for (int i = 0; i < k && n != null; i++)
n = n.next;
if (n == null)
break;
for (int i = 0; i < k - 1; i++) {
cur = node.next;
node.next = cur.next;
cur.next = n.next;
n.next = cur;
}
}
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
25
26
27
28
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class RotateLIst_61 {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null)
return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode left = dummy, right = dummy, br = dummy;
int length = 0;
while (right.next != null) {
length++;
right = right.next;
}
for (int j = length - k%length; j> 0; j--)
left = left.next;
right.next = dummy.next;
dummy.next = left.next;
left.next = null;
return dummy.next;
}
}

成对交换节点, 添加dummy节点,

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
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class SwapNodewsInPairs_24 {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode node1, node2, next;
while (pre.next != null && pre.next.next != null) {
node1 = pre.next;
node2 = node1.next;
next = node2.next;
node2.next = node1;
node1.next = next;
pre.next = node2;
//靠后的一对节点
pre = node1;
}
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package leetcode.linkedList;
/**
* Created by cdx0312
* 2018/4/7
*/
public class PalindromeLinkedList_234 {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null)
return true;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow.next = reverseList(slow.next);
fast = slow.next;
ListNode node = head;
while (fast != null) {
if (node.val != fast.val)
return false;
node = node.next;
fast = fast.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
if (head == null)
return head;
ListNode p = head.next;
head.next = null;
while (p != null) {
ListNode tmp = p;
p = p.next;
tmp.next = head;
head = tmp;
}
return head;
}
}
Donate comment here