链表问题_链表中倒数第K个节点

水深无声 2022-05-21 01:41 189阅读 0赞

题目：输入一个链表，输出该链表中倒数第k个节点。尾节点为倒数第一个节点。  
分析：可以采用两个指针，记为start和end，先让end在链表上走k-1步，然后两个节点同时开始走，当end到达尾节点时，start即为倒数第k个节点。这相当于做了一个长度为k的标尺一样，虽然很简单，但是在涉及到指针的操作时，一定要注意代码的鲁棒性，具体如下：

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                val(x), next(NULL) {
        }
    };*/
      ListNode* FindKthToTail(ListNode*phead, unsigned int k)
      {
          if (phead == NULL || k == 0)
              return NULL;
    
          ListNode*p_start = phead;
          ListNode*p_end = phead;
          for (int i = 0; i < k-1; i++)
          {
              if (p_end->next)
                  p_end = p_end->next;
              else
                  return NULL;
          }
    
          while (p_end->next!=NULL)
          {
              p_start = p_start->next;
              p_end = p_end->next;
          }
          return p_start;
      }

**说明：在这里函数的输入的参数k是一个无符号数，所以在判断输入是否合法时要判断k是否为0，因为一个无符号数0减去1之后值不是-1，而是0XFFFFFFFF，这样循环的次数无法预计。此外在里面使用指针时，一定要事先检查指针是否为空。**

相关问题：  
1、求链表的中间节点。如果链表中结点总数为奇数，返回中间节点；如果节点数为偶数，返回中间结点中的任一个。这里同样，我们可以使用两个指针，从链表的头部出发，一个指针走一步，另一个指针走两步。当走的快的指针到达链表末尾时，走的慢的指针刚好在链表中间。  
2、判断一个单向链表中是否有环形结构。和前面问题一样，定义两个指针，同时从链表的头部出发，一个指针一次走一步，一个指针一次走两步。如果走的快的指针追上了走的慢的指针那么链表就是环形结构；如果走的快的指针走到了链表的末尾都没有追上走的慢的指针，那么就没有环形结构。