快慢指針，顧名思義，就是操作鏈表的時候，使用兩個指針，一快一慢。靈活使用快慢指針，可以巧妙的解決很多問題。本文將介紹如下問題：

• 找到鏈表中的倒數(shù)第K個節(jié)點(diǎn)(leetCode 劍指offer22)；
• 找到鏈表的中點(diǎn)；
• 刪除鏈表倒數(shù)第K個節(jié)點(diǎn)；
• 判斷鏈表是否有環(huán)

先定義一個鏈表類：

public class ListNode {
 int val;
 ListNode next;
 ListNode(int x) {
  val = x;
 }
}

一、找到鏈表的倒數(shù)第K個節(jié)點(diǎn)

1. 題目描述：

假如現(xiàn)有如下鏈表，且k = 2：

1 --> 2 --> 3 --> 4 --> 5 --> 6

那么則應(yīng)輸出(倒數(shù)第K個節(jié)點(diǎn)，而不是倒數(shù)第K個節(jié)點(diǎn)的值)：

5 --> 6

2. 題目分析：

• 定義兩個指針，一個fast，一個slow，一開始都在第一個位置；
• 假設(shè)鏈表長度為n，倒數(shù)第k個，那么就是順數(shù)第n-k+1個，需要移動的步數(shù)就是n-k；
• 讓fast先走k步，此時fast離鏈表尾就還有n-k步；
• 然后讓slow和fast同時向后移動，當(dāng)fast移動到最后的時候，slow就移動了n-k步，就找到了目標(biāo)節(jié)點(diǎn)。

3. 代碼實(shí)現(xiàn)：

public ListNode getKthFromEnd(ListNode head, int k) {
 ListNode fast = head;
 ListNode slow = head;
 for(int i=0; i<k; i++) {
  fast = fast.next;
 }
 while(fast != null) {
  fast = fast.next;
  slow = slow.next;
 }
 return slow;
}

二、找到鏈表的中點(diǎn)

1. 題目描述：

輸入鏈表：

1 --> 2 --> 3 --> 4 --> 5 --> 6

則應(yīng)輸出：

4 --> 5 --> 6

輸入：

1 --> 2 --> 3 --> 4 --> 5

輸出：

3 --> 4 --> 5

2. 題目分析：

• 定義兩個指針，一個fast，一個slow，一開始都在第一個位置；
• 然后同時移動兩個指針，讓fast比slow快一倍，當(dāng)fast到尾了，slow就剛好在中點(diǎn)。

3. 代碼實(shí)現(xiàn)：

public ListNode getMiddle(ListNode head) {
 ListNode fast = head;
 ListNode slow = head;
 while(fast != null && fast.next != null) {
  fast = fast.next.next;
  slow = slow.next;
 }
 return slow;
}

三、刪除鏈表倒數(shù)第K個節(jié)點(diǎn)

1. 題目描述：

輸入如下鏈表，且k = 2：

1 --> 2 --> 3 --> 4 --> 5 --> 6

輸出：

1 --> 2 --> 3 --> 4 --> 6

2. 題目分析：

• 定義兩個指針，一個fast，一個slow，一開始都在第一個位置；
• 要刪除倒數(shù)第k個節(jié)點(diǎn)，就要找到它的前一個節(jié)點(diǎn)，即倒數(shù)第k+1個節(jié)點(diǎn)，順數(shù)就是(n-k-1)；
• 所以讓fast快k+1步，等fast到尾的時候，slow就在(n-k-1)的位置。

3. 代碼實(shí)現(xiàn)：

public ListNode delFromEnd(ListNode head, int k) {
 ListNode fast = head;
 ListNode slow = head;
 // 讓fast比slow快k步
 for(int i=0; i<k+1; i++) {
  fast = fast.next;
 }
 // 將slow移到倒數(shù)k+1位置，經(jīng)過該步驟，slow指向要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
 while(fast != null) {
  fast = fast.next;
  slow = slow.next;
 }
 // 這里讓前一個節(jié)點(diǎn)的next等于要刪除節(jié)點(diǎn)的next，就將要刪除的節(jié)點(diǎn)刪除了
 slow.next = slow.next.next;
 return head;
}

四、判斷鏈表是否有環(huán)

1. 題目描述：

如果輸入的是環(huán)形鏈表，則輸出true，反之輸出false。

2. 題目分析：

兩個人在環(huán)形跑道上跑步，從同一起點(diǎn)出發(fā)，一個人速度快，一個人速度慢，不管他們的速度相差多少，只要是有速度差，他們總有再次相遇的時刻。所以，我們可以使用快慢指針，判斷鏈表是否有環(huán)。如果兩個指針會再次相遇，就是有環(huán)，反之無。

3. 代碼實(shí)現(xiàn)：

public boolean hasCircle(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;
}

怎么樣，關(guān)于快慢指針，大家學(xué)廢了嗎