Skip to content

Commit 9c0c0b1

Browse files
dairongpengdairongpeng
committed
快慢指针解决链表问题
1 parent 5e411ce commit 9c0c0b1

File tree

1 file changed

+72
-169
lines changed

1 file changed

+72
-169
lines changed

‎06-链表相关高频题总结.md

Lines changed: 72 additions & 169 deletions
Original file line numberDiff line numberDiff line change
@@ -34,8 +34,10 @@
3434
```Go
3535
package main
3636

37+
import "fmt"
38+
3739
type Node struct {
38-
Val int
40+
Val int
3941
Next *Node
4042
}
4143

@@ -48,11 +50,10 @@ func NewLinkedList(val int) (head *Node) {
4850
}
4951

5052
// MidOrUpMidNode 给定一个链表的头节点
51-
// 1. 奇数长度返回中点
52-
// 2. 偶数长度返回上中点
53+
// 1. 奇数长度返回中点, 偶数长度返回上中点
5354
func (head *Node) MidOrUpMidNode() *Node {
5455
// 该链表没有点，有一个点，有两个点的时候都是返回头结点
55-
if head==nil || head.Next == nil || head.Next.Next == nil {
56+
if head == nil || head.Next == nil || head.Next.Next == nil {
5657
return head
5758
}
5859

@@ -67,182 +68,84 @@ func (head *Node) MidOrUpMidNode() *Node {
6768
}
6869
return slow
6970
}
70-
```
71-
72-
73-
74-
75-
76-
```Java
77-
package class06;
78-
79-
import java.util.ArrayList;
80-
81-
public class Code01_LinkedListMid {
82-
83-
public static class Node {
84-
public int value;
85-
public Node next;
86-
87-
public Node(int v) {
88-
value = v;
89-
}
90-
}
91-
92-
// head 头
93-
// 1、奇数长度返回中点，偶数长度返回上中点
94-
public static Node midOrUpMidNode(Node head) {
95-
// 没有点，有一个点，有两个点的时候都是返回头结点
96-
if (head == null || head.next == null || head.next.next == null) {
97-
return head;
98-
}
99-
// 链表有3个点或以上
100-
// 快慢指针，快指针一次走两步，慢指针一次走一步
101-
// 快指针走完，慢指针在中点位置
102-
Node slow = head.next;
103-
Node fast = head.next.next;
104-
while (fast.next != null && fast.next.next != null) {
105-
slow = slow.next;
106-
fast = fast.next.next;
107-
}
108-
return slow;
109-
}
110-
111-
// 2、奇数长度返回中点，偶数长度返回中下点
112-
public static Node midOrDownMidNode(Node head) {
113-
if (head == null || head.next == null) {
114-
return head;
115-
}
116-
Node slow = head.next;
117-
Node fast = head.next;
118-
while (fast.next != null && fast.next.next != null) {
119-
slow = slow.next;
120-
fast = fast.next.next;
121-
}
122-
return slow;
123-
}
12471

125-
// 3、奇数长度返回中点前一个，偶数长度返回上中点前一个
126-
public static Node midOrUpMidPreNode(Node head) {
127-
if (head == null || head.next == null || head.next.next == null) {
128-
return null;
129-
}
130-
Node slow = head;
131-
Node fast = head.next.next;
132-
while (fast.next != null && fast.next.next != null) {
133-
slow = slow.next;
134-
fast = fast.next.next;
135-
}
136-
return slow;
72+
// MidOrDownMidNode 给定一个链表的头节点
73+
// 2、奇数长度返回中点，偶数长度返回中下点
74+
func (head *Node) MidOrDownMidNode() *Node {
75+
// 该链表没有点，有一个点, 返回头结点
76+
if head == nil || head.Next == nil {
77+
return head
13778
}
138-
139-
// 4、奇数长度返回中点前一个，偶数长度返回下中点前一个
140-
public static Node midOrDownMidPreNode(Node head) {
141-
if (head == null || head.next == null) {
142-
return null;
143-
}
144-
if (head.next.next == null) {
145-
return head;
146-
}
147-
Node slow = head;
148-
Node fast = head.next;
149-
while (fast.next != null && fast.next.next != null) {
150-
slow = slow.next;
151-
fast = fast.next.next;
152-
}
153-
return slow;
79+
slow := head.Next
80+
fast := head.Next
81+
for fast.Next != nil && fast.Next.Next != nil {
82+
slow = slow.Next
83+
fast = fast.Next.Next
15484
}
85+
return slow
86+
}
15587

156-
// 笔试可以用这种复杂点的方法，空间复杂度比上面快慢指针要高
157-
public static Node right1(Node head) {
158-
if (head == null) {
159-
return null;
160-
}
161-
Node cur = head;
162-
ArrayList<Node> arr = new ArrayList<>();
163-
while (cur != null) {
164-
arr.add(cur);
165-
cur = cur.next;
166-
}
167-
return arr.get((arr.size() - 1) / 2);
88+
// MidOrUpMidPreNode 给定一个链表的头节点
89+
// 3、奇数长度返回中点前一个，偶数长度返回上中点前一个
90+
func (head *Node) MidOrUpMidPreNode() *Node {
91+
// 该链表没有点，有一个点, 有两个点， 返回头结点
92+
if head == nil || head.Next == nil || head.Next.Next == nil {
93+
return nil
16894
}
169-
170-
public static Node right2(Node head) {
171-
if (head == null) {
172-
return null;
173-
}
174-
Node cur = head;
175-
ArrayList<Node> arr = new ArrayList<>();
176-
while (cur != null) {
177-
arr.add(cur);
178-
cur = cur.next;
179-
}
180-
return arr.get(arr.size() / 2);
95+
slow := head
96+
fast := head.Next.Next
97+
for fast.Next != nil && fast.Next.Next != nil {
98+
slow = slow.Next
99+
fast = fast.Next.Next
181100
}
101+
return slow
102+
}
182103

183-
public static Node right3(Node head) {
184-
if (head == null || head.next == null || head.next.next == null) {
185-
return null;
186-
}
187-
Node cur = head;
188-
ArrayList<Node> arr = new ArrayList<>();
189-
while (cur != null) {
190-
arr.add(cur);
191-
cur = cur.next;
192-
}
193-
return arr.get((arr.size() - 3) / 2);
104+
// MidOrDownMidPreNode 给定一个链表的头节点
105+
// 4、奇数长度返回中点前一个，偶数长度返回下中点前一个
106+
func (head *Node) MidOrDownMidPreNode() *Node {
107+
if head == nil || head.Next == nil {
108+
return nil
194109
}
195-
196-
public static Node right4(Node head) {
197-
if (head == null || head.next == null) {
198-
return null;
199-
}
200-
Node cur = head;
201-
ArrayList<Node> arr = new ArrayList<>();
202-
while (cur != null) {
203-
arr.add(cur);
204-
cur = cur.next;
205-
}
206-
return arr.get((arr.size() - 2) / 2);
110+
if head.Next.Next == nil {
111+
return head
207112
}
208-
209-
public static void main(String[] args) {
210-
Node test = null;
211-
test = new Node(0);
212-
test.next = new Node(1);
213-
test.next.next = new Node(2);
214-
test.next.next.next = new Node(3);
215-
test.next.next.next.next = new Node(4);
216-
test.next.next.next.next.next = new Node(5);
217-
test.next.next.next.next.next.next = new Node(6);
218-
test.next.next.next.next.next.next.next = new Node(7);
219-
test.next.next.next.next.next.next.next.next = new Node(8);
220-
221-
Node ans1 = null;
222-
Node ans2 = null;
223-
224-
ans1 = midOrUpMidNode(test);
225-
ans2 = right1(test);
226-
System.out.println(ans1 != null ? ans1.value : "无");
227-
System.out.println(ans2 != null ? ans2.value : "无");
228-
229-
ans1 = midOrDownMidNode(test);
230-
ans2 = right2(test);
231-
System.out.println(ans1 != null ? ans1.value : "无");
232-
System.out.println(ans2 != null ? ans2.value : "无");
233-
234-
ans1 = midOrUpMidPreNode(test);
235-
ans2 = right3(test);
236-
System.out.println(ans1 != null ? ans1.value : "无");
237-
System.out.println(ans2 != null ? ans2.value : "无");
238-
239-
ans1 = midOrDownMidPreNode(test);
240-
ans2 = right4(test);
241-
System.out.println(ans1 != null ? ans1.value : "无");
242-
System.out.println(ans2 != null ? ans2.value : "无");
243-
113+
slow := head
114+
fast := head.Next
115+
for fast.Next != nil && fast.Next.Next != nil {
116+
slow = slow.Next
117+
fast = fast.Next.Next
244118
}
119+
return slow
120+
}
245121

122+
func main() {
123+
// 0 1
124+
// 0 1 2
125+
// 0 1 2 3
126+
// 0 1 2 3 4
127+
// 0 1 2 3 4 5
128+
// 0 1 2 3 4 5 6
129+
// 0 1 2 3 4 5 6 7
130+
// 0 1 2 3 4 5 6 7 8
131+
hd := &Node{}
132+
hd.Next = &Node{Val: 1}
133+
hd.Next.Next = &Node{Val: 2}
134+
hd.Next.Next.Next = &Node{Val: 3}
135+
hd.Next.Next.Next.Next = &Node{Val: 4}
136+
hd.Next.Next.Next.Next.Next = &Node{Val: 5}
137+
hd.Next.Next.Next.Next.Next.Next = &Node{Val: 6}
138+
hd.Next.Next.Next.Next.Next.Next.Next = &Node{Val: 7}
139+
// hd.Next.Next.Next.Next.Next.Next.Next.Next = &Node{Val: 8}
140+
141+
ans1 := hd.MidOrUpMidNode()
142+
fmt.Println(fmt.Sprintf("1.奇数长度返回中点，偶数长度返回上中点: %d", ans1.Val))
143+
ans2 := hd.MidOrDownMidNode()
144+
fmt.Println(fmt.Sprintf("2.奇数长度返回中点，偶数长度返回中下点: %d", ans2.Val))
145+
ans3 := hd.MidOrUpMidPreNode()
146+
fmt.Println(fmt.Sprintf("3.奇数长度返回中点前一个，偶数长度返回上中点前一个: %d", ans3.Val))
147+
ans4 := hd.MidOrDownMidPreNode()
148+
fmt.Println(fmt.Sprintf("4.奇数长度返回中点前一个，偶数长度返回下中点前一个: %d", ans4.Val))
246149
}
247150
```
248151

0 commit comments

Comments
 (0)