输入一个链表,输出其倒数第k个节点

1、设两个指针slow和quick,当i<k-1 时slow移动,quick不动。当i>=k-1 时quick也开始同频率移动;
2、当slow移动到正序第k个,quick移动到正序第一个;
3、当slow移动到倒序第一个,quick移动到 倒序第k个;
4、return quick

 * 题目:给出链表 {1,2,3,4,5,6,7},输出倒序第5个
 * 当slow移动到5,quick移动到1 
 * 当slow移动到7,quick移动到3(倒数第5个)
 * 1 2 3 4 5 6 7
 * q       s        # 开始时slow=5;quick=1
 *     q       s    # 结束时show+2=7;quick+2=3

注意:

  1. 输入链表不能为空;
  2. k不大于链表长度;
class NodeList{
  int val;
  NodeList next = null;
  NodeList(int val){
    this.val = val;
  }
}
public class Solution{
     
    public ListNode FindKthTotail(ListNode head, int k){
        # 链表不为空
        if(k == 0 || head == null){
            return null;
        }
        ListNode temp = head;
        # 链表长度不小于 k-1,头结点已经验证过了
        for(int i = 0; i < k-1; i++){
            if(temp.next != null){
                temp = temp.next;
            }else{
                return null;
            }
        }
        ListNode quick = head;
        ListNode slow = head;
        #当 i < k-1 时,slow 指针动,quick 指针不动;
        for(int i = 0; i < k-1; i++){
            slow = slow.next;
        }
        while(slow.next!=null){
            slow=slow.next;
            quick=quick.next;
        }
        return quick;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容