思路：
维护两个链表，遍历原链表，小于x的接入第一个链表，不小于x的接入第二个链表，再合并两链表
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
|
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class {
public ListNode partition(ListNode head, int x) {
ListNode newHead = new ListNode(0);
ListNode dummy = new ListNode(0);
ListNode p = newHead;
ListNode q = dummy;
while (head != null) {
if (head.val < x) {
p.next = head;
p = p.next;
} else {
q.next = head;
q = q.next;
}
head = head.next;
}
p.next = dummy.next;
q.next = null;
return newHead.next;
}
}
|
思路：
分成三步：
- 找链表的中间结点，切成两条链表（head, tail）
- 反转链表tail
- 合并链表head和tail，合并条件：奇数为head，偶数为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
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
61
62
63
64
65
|
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class {
public ListNode findMiddle(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public ListNode reverse(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode temp = head.next;
head.next = newHead;
newHead = head;
head = temp;
}
return newHead;
}
public void merge(ListNode head, ListNode tail) {
ListNode newHead = new ListNode(0);
ListNode p = newHead;
int n = 0;
while (head != null && tail != null) {
if (n % 2 == 0) {
p.next = head;
head = head.next;
} else {
p.next = tail;
tail = tail.next;
}
p = p.next;
n++;
}
if (head != null) {
p.next = head;
} else {
p.next = tail;
}
}
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode middle = findMiddle(head);
ListNode tail = middle.next;
middle.next = null;
tail = reverse(tail);
merge(head, tail);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode p = dummyHead;
while (p.next != null) {
if (p.next.val == val) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return dummyHead.next;
}
}
|
近期评论