剑指Offer_22_链表中倒数第k个节点

题目1描述：

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

解法1：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {

        if (head == NULL || k == 0) return NULL;

        ListNode *pAhead = head;
        ListNode *pBehind = NULL;

        for (int i = 0;i < k-1;++i) {

            //如果链表的节点数少于k，那么在for循环中遍历链表可能会出现指向NULL的next
            if (pAhead -> next != NULL) {

                pAhead = pAhead -> next;
            } else {

                return NULL;
            }
        }

        pBehind = head;

        while (pAhead -> next != NULL) {
            
            pAhead = pAhead -> next;
            pBehind = pBehind -> next;
        }

        return pBehind; 
    }
};

❗️LeetCode_876_链表的中间节点

题目2描述：

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

解法1：

//这道题目其实是上面题目的特殊示例，完全可以用上面的方法解决，但是因为没有给出k值，所以需要遍历一遍链表求出链表的长度。针对此题更简单的解题思路是：我们可以定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步，当走得快的指针走到链表的末尾时，走的慢的指针正好在链表的中间

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {

        if (head == NULL) return NULL;

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

        while(fast != NULL && fast->next != NULL) {

            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};