美文网首页
输入一个链表,输出其倒数第k个节点

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

作者: bfx1000 | 来源:发表于2019-10-03 09:34 被阅读0次

    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;
        }
    }
    

    相关文章

      网友评论

          本文标题:输入一个链表,输出其倒数第k个节点

          本文链接:https://www.haomeiwen.com/subject/wtnfuctx.html