思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class {
public ListNode reverseList(ListNode head) {
ListNode p = null;
ListNode temp;
while(head != null) {
temp = head.next;
head.next = p;
p = head;
head = temp;
}
return p;
}
}
|
思路：
m的前一个节点作为头节点，使用头插法插入m~n之间的节点，最后将m的下一个节点调整为n之后的节点
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
|
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || head.next == null)
return head;
ListNode fakeHead = new ListNode(0);
ListNode start = fakeHead;
fakeHead.next = head;
for (int i = 0; i < m - 1; i++) {
start = start.next;
}
ListNode end = start.next;
ListNode p = start.next.next;
ListNode q = p;
for(int i = 0; i < n - m; i++) {
q = p;
p = p.next;
q.next = start.next;
start.next = q;
}
end.next = p;
return fakeHead.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
|
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
}
|
思路：
- 快慢指针查找相遇点
- 慢指针回到起点，快慢指针每次移动一步
- 快慢指针再次相遇点即为链表环入口
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
|
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
boolean flag = false;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
flag = true;
break;
}
}
if (flag == false)
return null;
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
|
近期评论