链表中倒数第k个结点

╰+哭是因爲堅強的太久メ 2022-06-07 12:26 119阅读 0赞

链接： [https://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a][https_www.nowcoder.com_questionTerminal_529d3ae5a407492994ad2a246518148a]  
来源：牛客网

*  热度指数：255270 时间限制：1秒 空间限制：32768K

输入一个链表，输出该链表中倒数第k个结点。

分析：当链表为空或k<1时，直接返回null。从头到尾循环链表，每移动一次，k值减1。定义两个指针，指针cur用于循环链表，指针ans返回倒数第k个结点。链表循环结束后根据k值进行分析：

（1）当k==0时，链表元素的个数等于k，倒数第k个结点即为链表的第一个元素；

（2）当k<0时，链表元素的个数大于k，该情况下链表循环结束后k为负值。从头开始遍历链表，直至k = 0，此时指针ans.next即为所求；

（3）当k>0时，链表元素的个数小于k，此时不存在链表的第k个结点，直接返回null。

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode FindKthToTail(ListNode head,int k) {
            if(head == null || k < 1)
                return null;
            ListNode cur = head;
            ListNode ans = head; 
            
            while(cur != null){
            	k--;
            	cur = cur.next;
            }
            if(k == 0)
            	return ans;
            else if(k < 0){
            	while(++k != 0){
            		ans = ans.next;
            	}
            	return ans.next;
            }
            return null;
            
             }
    }

还有一种思路是参考讨论中 [菩提旭光][https_www.nowcoder.com_questionTerminal_529d3ae5a407492994ad2a246518148a]的回答：两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指针走(k-1)步，到达第k个节点。然后两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了。

public class Solution{
    
    	public static ListNode FindKthToTail(ListNode head,int k) {
    		if(head == null || k < 1)
                return null;
            ListNode cur = head;
            ListNode ans = head; 
            
            for(int i = 0;i < k;i++){
    			if(cur != null)
                    cur = cur.next;
                else
                    return null;
            }
            while(cur != null){
                cur = cur.next;
                ans = ans.next;
            }
            return ans;
    	}
    }

[https_www.nowcoder.com_questionTerminal_529d3ae5a407492994ad2a246518148a]: https://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a