203 移除链表元素
利用dummy node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return head;
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
ListNode cur = head;
while (cur != null){
if (cur.val == val){
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
}
|
利用递归
判断返回条件，把下一个值做成条件，确定一个循环的逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return head;
head.next = removeElements(head.next,val);
if (head.val == val){
return head.next;
} else {
return head;
}
}
}
|
707 设计链表
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
66
67
68
69
70
71
72
73
| class ListNode{
int val;
ListNode next;
ListNode(){}
ListNode(int val){
this.val = val;
}
ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
this.size = 0;
this.head = new ListNode(0);
}
public int get(int index) {
if (index < 0 || index > size - 1){
return -1;
}
ListNode cur = head;
for (int i = 0; i <= index; i++){
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if (index < 0) index = 0;
if (index > size) return;
size++;
ListNode newNode = new ListNode(val);
ListNode pre = head;
for (int i = 0; i < index; i++){
pre = pre.next;
}
newNode.next = pre.next;
pre.next = newNode;
}
public void deleteAtIndex(int index) {
if (index < 0 || index > size - 1) return;
size--;
ListNode pre = head;
for (int i = 0; i < index; i++){
pre = pre.next;
}
pre.next = pre.next.next;
}
}
|
206 翻转链表
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
|
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public ListNode reverseList(ListNode head) {
return reverse(head, null);
}
private ListNode reverse(ListNode cur, ListNode prev){
if (cur == null) return prev;
ListNode temp = cur.next;
cur.next = prev;
return reverse(temp, cur);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
if (head != null && head.next == null) return head;
ListNode next = reverseList(head.next);
head.next.next = head;
head.next = null;
return next;
}
}
|
24 两两交换链表中的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null){
ListNode firstNode = cur.next;
ListNode secondNode = cur.next.next;
ListNode temp = cur.next.next.next;
cur.next = secondNode;
secondNode.next = firstNode;
firstNode.next = temp;
cur = firstNode;
}
return dummy.next;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode next = head.next;
ListNode newNode = swapPairs(next.next);
next.next = head;
head.next = newNode;
return next;
}
}
|
19 删除链表的倒数第N个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution{
public ListNode removeNthFromEnd(ListNode head, int n){
ListNode dummy = new ListNode(0, head);
ListNode slowIndex = dummy;
ListNode fastIndex = dummy;
for (int i = 0; i <= n; i++) fastIndex = fastIndex.next;
while(fastIndex != null){
fastIndex = fastIndex.next;
slowIndex = slowIndex.next;
}
slowIndex.next = slowIndex.next.next;
return dummy.next;
}
}
|
160 链表相交
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 class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenHeadA = 0;
int lenHeadB = 0;
ListNode curA = headA;
ListNode curB = headB;
while (curA != null){
lenHeadA++;
curA = curA.next;
}
while (curB != null){
lenHeadB++;
curB = curB.next;
}
curA = headA;
curB = headB;
if (lenHeadA > lenHeadB){
for (int i = 0; i < lenHeadA - lenHeadB; i++){
curA = curA.next;
}
} else {
for (int i = 0; i < lenHeadB - lenHeadA; i++){
curB = curB.next;
}
}
while (curA != null){
if (curA == curB){
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
|
142 链表相交
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if (fast == slow){
ListNode cur = head;
while (cur != slow){
cur = cur.next;
slow = slow.next;
}
return cur;
}
}
return null;
}
}
|