寻找链表的中间节点
利用快慢指针，开始两个指针都指向头，快指针每次前进两步，慢指针每次前进一步。快指针达到终点时，慢指针刚好达到中点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public static ListNode MiddleNode(ListNode head)
{
if (head == null || head.next == null) return head;
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null)
{
fast = fast.next.next;
slow = slow.next;
}
if (fast.next != null)
{
fast = fast.next;
slow = slow.next;
}
return new ListNode(slow.val);
}
|
倒数第n个节点
倒数第N个节点的查找与删除。同样是利用快慢指针，先让快指针先走N步，然后快慢指针同时向前走，直到快指针达到终点，此时慢指针指向倒数第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
|
public static ListNode TrainingPlan(ListNode head, int cnt)
{
if (head == null || head.next == null) return head;
ListNode virsualNode = new ListNode(int.MinValue);
virsualNode.next = head;
ListNode fast = virsualNode;
ListNode tail = virsualNode;
while (fast != null && cnt > 0)
{
fast = fast.next;
--cnt;
}
if (fast == null) return null;
while (fast.next != null)
{
fast = fast.next;
tail = tail.next;
}
return tail.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
|
public static ListNode RemoveNthFromEnd(ListNode head, int n)
{
if (head == null) return head;
ListNode virsualNode = new ListNode(int.MinValue);
virsualNode.next = head;
ListNode fast = virsualNode;
ListNode tail = virsualNode;
while (fast != null && n > 0)
{
fast = fast.next;
--n;
}
if (fast == null) return null;
while (fast.next != null)
{
fast = fast.next;
tail = tail.next;
}
tail.next = tail.next.next;
return virsualNode.next;
}
|
合并有序链表
合并两个链表很简单，精华在下面合并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
|
public static ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode virsualNode = new ListNode(int.MinValue);
ListNode result = virsualNode;
while (l1 != null && l2 != null)
{
if (l1.val <= l2.val)
{
virsualNode.next = l1;
l1 = l1.next;
}
else
{
virsualNode.next = l2;
l2 = l2.next;
}
virsualNode = virsualNode.next;
}
if (l1 == null) virsualNode.next = l2;
else virsualNode.next = l1;
return result.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
|
public static ListNode MergeKLists(ListNode[] lists)
{
ListNode start = new ListNode(int.MinValue);
ListNode result = start;
int nullCount = 0;
while (nullCount < lists.Length)
{
nullCount = 0;
int minIndex = -1;
int minValue = int.MaxValue;
for (int i = 0; i < lists.Length; i++)
{
if (lists[i] == null) { ++nullCount; continue; }
if (lists[i].val <= minValue)
{
minValue = lists[i].val;
minIndex = i;
}
}
if (minIndex == -1) break;
start.next = lists[minIndex];
lists[minIndex] = lists[minIndex].next;
start = start.next;
}
return result.next;
}
|
两个链表是否相交
画个图好理解：
将两个链表分别连接下对方，如下：
此时两个链表长度相同。然后两个链表都开始向尾部移动，如果两个指针相同就说明是共公节点。如果链表遍历结束没有出现相同节点，则说明两个链表没有公共节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public static ListNode GetIntersectionNode(ListNode headA, ListNode headB)
{
ListNode AA = headA;
ListNode BB = headB;
while (AA != BB)
{
AA = AA != null ? AA.next : headB;
BB = BB != null ? BB.next : headA;
}
return AA;
}
|
链表是否包含环
是否有环，同样快慢指针
快指针每次向前两步，慢指针每次向前一步，
- 如果这个链表有环：快指针会与慢指针重合
- 遍历到结尾也没重合，说明没有环。
找到环的起点
利用上面方式找到相同节点后。我们知道快指针走过的距离是慢指针的2倍，假设快指针走了2k,慢指针走了k，那么环的大小就是k。
- 将 快/慢指针 任意一个回到头节点。
- 然后两个只能都每次走1步。
- 两个指针相交时就是环的开始节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static bool HasCycle(ListNode head)
{
if (head == null || head.next == null) return false;
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
|
public static ListNode DetectCycle(ListNode head)
{
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
if (fast == null || fast.next == null) return null;
fast = head;
while (fast != slow)
{
fast = fast.next;
slow = slow.next;
}
return fast;
}
|
