访问链表中的某个元素（快慢指针）

题目一：访问中间元素

题目信息：

（1）题目连接：

leetcode中间元素访问

（2）题目信息：

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
1
2
3

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes 
with values 3 and 4,
 we return the second one.
1
2
3
4
5

Constraints:

The number of nodes in the list is in the range [1, 100].
1 <= Node.val <= 100
1
2

题目解答：

（1）方法一：遍历

这种方法是最容易想到的，第一遍遍历计算节点的个数，第二遍遍历找到中间的节点。
这个方法由于过于简单，并且我也懒得画图了，所以就不作图解了。直接上代码：

/*
 * Definition for singly-linked list.
 * struct ListNode 
 * {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head)
{
    if(head==NULL)
    {
        return NULL;
    }
    int count=1;
    struct ListNode*tail=head;
    while(tail->next!=NULL)
    {
        tail=tail->next;
        count++;
    }

    int mid=(count/2)+1;
    int n=1;
    struct ListNode*cur=head;
    while(n!=mid)
    {
        if(cur!=NULL)
        cur=cur->next;
        n++;
    }
    return cur;

}
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

那么我们能只遍历一遍就得到结果吗？此时我们就需要了解一下方法二。

（1）方法二：快慢指针

当节点个数为奇数的时候：

当节点个数为偶数的时候：

/*
 * Definition for singly-linked list.
 * struct ListNode
 * {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode*quick=head,*slow=head;
    while(quick!=NULL&&quick->next!=NULL)
    {
        slow=slow->next;
        quick=quick->next->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题目二：访问倒数第K个元素

题目信息：

leetcode访问倒数第k个元素

题目详解：

这道题并不是类似访问中间节点，或者三分之一节点的倍数问题，所以我们的快慢指针不能快在步长。那么我们如何使用快慢指针呢？

如下图所示，此时我们设置的两个快慢指针的步长都设置为一个节点。但是我们要让快指针提前出发k个节点。

（1）图解

（2）代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
 {
     if(pListHead==NULL)
     {
         return NULL;
     }
    struct ListNode *tail=pListHead;
    int count=1;
    while(tail->next!=NULL)
    {
        tail=tail->next;
        count++;
    } 
    if(k>count||k<=0)
    {
        return NULL;
    }
    else
    {
        struct ListNode *slow=pListHead;
        struct ListNode *quick=pListHead;
        while(k--)
        {
            quick=quick->next;
        }
        while(quick!=NULL)
        {
            slow=slow->next;
            quick=quick->next;
        }
        return slow;
    }

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

我们需要格外注意 k范围和空链表的判断！