精华内容
下载资源
问答
  • 链表中倒数第k个节点

    2019-08-27 15:25:13
    链表中倒数第k个节点 输入一个链表,输出该链表中倒数第k个结点。 public class LinkedList { public Node head; public Node current; public static void main(String[] args) { // TODO Auto-generated ...

    链表中倒数第k个节点

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

    
    public class LinkedList {
    
    	public Node head;
    	public Node current;
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		LinkedList list = new LinkedList();// 新建一个单链表
    		// 向LinkedList中添加数据
    		for (int i = 0; i < 10; i++) {
    			list.add(i);// 向链表中添加数据
    		}
    		Node result = FindKthToTail(list.head, 1);
    		System.out.println(result.data);
    	}
    
    	public static Node FindKthToTail(Node head, int k) {
    		if (k <= 0)
    			return null;
    		Node p1 = head;
    		Node p2 = head;
    		// p2向前移动k个节点
    		for (int i = 0; i < k - 1; i++) {
    			if (p2 == null)
    				return null;
    			p2 = p2.next;
    		}
    		if (p2 == null)
    			return null;
    		while (p2.next != null) {
    			p1 = p1.next;
    			p2 = p2.next;
    		}
    		return p1;
    
    	}
    
    	// 方法:向链表中添加数据
    	public void add(int data) {
    		// 判断链表为空的时候
    		if (head == null) {// 如果头结点为空,说明这个链表还没有创建,那就把新的结点赋给头结点
    			head = new Node(data);
    			current = head;
    		} else {
    			// 创建新的结点,放在当前节点的后面(把新的结点和链表进行关联)
    			current.next = new Node(data);
    			// 把链表的当前索引向后移动一位
    			current = current.next; // 此步操作完成之后,current结点指向新添加的那个结点
    		}
    	}
    
    	// 节点类
    	class Node {
    		// 注:此处的两个成员变量权限不能为private,因为private的权限是仅对本类访问。
    		int data; // 数据域
    		Node next;// 指针域
    
    		public Node(int data) {
    			this.data = data;
    		}
    	}
    }
    
    
    展开全文
  • 输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表倒数第...

    链表中倒数第 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 步,然后 prePointerbehPointer 一起后移,直至 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
      
    展开全文
  • 链表中倒数第K个节点

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

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

    请看下面一段代码

    class Solution 
    {
    public:
    	ListNode* getKthFromEnd(ListNode* head, int k) 
    	{
    		if (head == nullptr || k == 0)
    		{
    			return nullptr;
    		}
    		ListNode* CurrentNode = head;
    		for (int i = 0; i < k; i++)
    		{
    			CurrentNode = CurrentNode->next;
    		}
    
    		while (CurrentNode)
    		{
    			//此时CurrentNode比head多走K个节点
    			CurrentNode = CurrentNode->next;
    			head = head->next;
    		}
    		return head;
    	}
    };
    

    上面的代码其实存在一些问题,如果以head为头结点的链表的节点数小于K,此时可能由于空指造成程序崩溃

    优后的代码(增强了鲁棒性)

    class Solution
    {
    public:
    	ListNode* getKthFromEnd(ListNode* head, int k)
    	{
    		if (head == nullptr || k == 0)
    		{
    			return nullptr;
    		}
    		ListNode* pHead = head;
    		ListNode* pNode = head;
    		for (int i = 0; i < k - 1; i++)
    		{
    			if (pHead->next != nullptr)
    			{
    				pHead = pHead->next;
    			}
    			else
    			{
    				return nullptr;
    			}
    		}
    		while (pHead->next != nullptr)
    		{
    			pHead = pHead->next;
    			pNode = pNode->next;
    		}
    		return pNode;
    	}
    };
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,375
精华内容 10,550
关键字:

链表中倒数第k个节点