链表中倒数第 k 个节点

港控/mmm° 2022-11-29 03:09 119阅读 0赞

# 链表中倒数第 k 个节点 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

## 2、题目要求 ##

> 题目描述

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

> **示例：**

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

## 3、代码思路 ##

> **方案一：先求得链表长度 `n`，最顺序遍历至第 `n-k` 个节点**

第一时间想到的解法：

1.  先遍历统计链表长度，记为 `n` ；
2.  设置一个指针走 `(n-k)` 步，即可找到链表倒数第 `k` 个节点。

> **方法二：双指针法**

定义双指针：前指针 `prePointer` 和后指针 `behPointer`

前指针 `prePointer` 和后指针 `behPointer` 永远相差 `k` 个节点，这样当 `behPointer` 指向链表末尾 `null` 时，`prePointer` 恰好指向倒数第 `k` 个节点

具体步骤为：前指针 `prePointer` 和后指针 `behPointer` 都指向链表首节点，`behPointer` 先向后移动 `k` 步，然后 `prePointer` 和 `behPointer` 一起后移，直至 `behPointer == null`

## 4、代码实现 ##

1.  代码
    
        public class LastKthNode {
              
        
        	public static void main(String[] args) {
              
        
        		SingleLinkedList singleLinkedList = new SingleLinkedList();
        
        		singleLinkedList.add(new Node(1));
        		singleLinkedList.add(new Node(2));
        		singleLinkedList.add(new Node(3));
        		singleLinkedList.add(new Node(4));
        		singleLinkedList.add(new Node(5));
        		singleLinkedList.add(new Node(6));
        
        		System.out.println("顺序输出~~~");
        		singleLinkedList.show();
        
        		Node lastKthNode = singleLinkedList.lastKthNode(6);
        		System.out.println("倒数第 k 个节点为：" + lastKthNode);
                
        	}
        
        }
        
        //链表类
        class SingleLinkedList {
              
        
        	private Node head = new Node(0);
        
        	public void add(Node node) {
              
        		// 首节点指针不能移动哦，需要定义辅助指针
        		Node preNode = head;
        		while (preNode.next != null) {
              
        			preNode = preNode.next;
        		}
        		preNode.next = node;
        	}
        
        	public void show() {
              
        		// 首节点指针不能移动哦，需要定义辅助指针
        		Node curNode = head.next;
        		while (curNode != null) {
              
        			System.out.print(curNode.data + "-->");
        			curNode = curNode.next;
        		}
        		System.out.println();
        	}
        
        	public Node lastKthNode(int k) {
              
        
        		// 目标：当 behPointer 指向 null 时，prePointer 指向倒数第 k 个节点
        		Node prePointer = head.next;
        		Node behPointer = head.next;
        		// behPointer 指针还需要向后移动多少步
        		int leftSteps = k;
        
        		// behPointer 向后移动 k 步
        		while (leftSteps > 0 && behPointer != null) {
              
        			behPointer = behPointer.next;
        			leftSteps -= 1;
        		}
        		
        		// 如果 behPointer 还未移动 k 步就已经是 null，则说明链表长度不足 k
        		if(leftSteps !=0) {
              
        			return null;
        		}
        		
        		// behPointer 和 prePointer 同时向后移动，当 behPointer 为 null 时，prePointer 则指向倒数第 k 个节点
        		while(behPointer!=null) {
              
        			behPointer = behPointer.next;
        			prePointer = prePointer.next;
        		}
        
        		// 返回倒数第 k 个节点
        		return prePointer;
        	}
        }
        
        //节点
        class Node {
              
        	public Integer data;
        	public Node next;
        
        	public Node(Integer data) {
              
        		this.data = data;
        	}
        
        	public String toString() {
              
        		return data.toString();
        	}
        }
2.  程序运行结果
    
        顺序输出~~~
        1-->2-->3-->4-->5-->6-->
        倒数第 k 个节点为：1