通过快慢指针法定位链表的中间结点

Question

给定一个头结点为head的非空单链表，返回链表的中间结点。若存在两个中间结点，则返回第二个中间结点。

链表的不足在于其无法通过下标直接访问特定结点，需要逐个遍历结点以定位特定结点。一般情况下，可以将链表中的数据内容逐个遍历至数组中，从而将链表转化为数组，进而直接输出数组下标为 的数组元素，但其代码比较繁杂。因此，本题采用更为巧妙的快慢指针法。

快慢指针法即同时设置一个快指针与一个慢指针对链表进行遍历，其中快指针一次遍历两个结点，慢指针一次遍历一个结点。当快指针最终指向链表末尾或NULL时，慢指针正好指向中间结点位置。

首先定义一个快指针与一个慢指针

struct ListNode* slow = head;
struct ListNode* fast = head;

在定义遍历循环前，需要首先确定循环终止条件。当结点数为奇数时，快指针最终会指向链表末尾，因此其循环为

while(fast->next != NULL){
  fast = fast->next->next;
  slow = slow->next;
}

当结点数为偶数时，慢指针最终会指向NULL，因此其循环为

while(fast != NULL){
  fast = fast->next->next;
  slow = slow->next;
}

故完整结构为

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Python下代码为

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution(object):
    def middleNode(self, head):
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow