专栏首页灰子学技术算法篇:链表之倒数第k个节点

算法篇:链表之倒数第k个节点

算法:

该类型的题目,核心点在于如何找到倒数第k个节点的位置,典型的操作办法是,双指针的方法。

第一个指针先偏移k个位置,第二个指针才开始执行
然后两个指针同时往后移动,第一个指针到链表尾部,第一个指针就是倒数第k个位置

题目 1 :链表中倒数第k个节点

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

代码实现:

// 算法:这是典型的双指针的做法,
// 第一个指针先偏移k个位置,第二个指针才开始执行
// 然后两个指针同时往后移动,第一个指针到链表尾部,第一个指针就是倒数第k个位置
/** 
* Definition for singly-linked list. 
* type ListNode struct { 
*     Val int 
*     Next *ListNode 
* } 
*/

func getKthFromEnd(head *ListNode, k int) *ListNode {
    c := head    
    for i:=0;i<k;i++ {   
         head = head.Next    
    }    
    for head != nil {   
         c = c.Next        
         head = head.Next    
    }    
    return c
}

执行结果:

题目2: 删除倒数第k个节点

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/submissions/

代码实现:

// 算法:该问题是题目1的变形题目,
// 采用题目1的算法找到倒数第k个节点的前序节点,然后删除倒数第k个节点
/** 
* Definition for singly-linked list. 
* type ListNode struct { 
*     Val int 
*     Next *ListNode 
* } 
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    head1 := head    
    head2 := head    
    for i:=n; i>0; i-- {    
        head2 = head2.Next    
    }    
    if head2 == nil {   
        head = head.Next        
        return head    
    }    
    for {    
        if head2.Next == nil {      
              break        
        }        
        head2 = head2.Next        
        head1 = head1.Next     
     }   
     // 获取到 倒数第n-1位置的节点   
     head1.Next = head1.Next.Next    
     return head
}

执行结果:

本文分享自微信公众号 - 灰子学技术(huizixueguoxue),作者:灰子学技术

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法篇:链表之反转链表

    https://leetcode-cn.com/problems/reverse-linked-list/

    灰子学技术
  • 算法篇:链表之排序

    https://leetcode-cn.com/problems/partition-list/submissions/

    灰子学技术
  • 算法篇:链表之合并有序链表

    算法的核心在于两个有序链表的合并操作,K个有序链表的合并只是一个变形题目,先拆分成k/2个有序链表,然后等比数列减少到1个数列。

    灰子学技术
  • 算法篇:链表之反转链表

    https://leetcode-cn.com/problems/reverse-linked-list/

    灰子学技术
  • 各种编程语言的优缺点

    文章转载自伯乐在线 原文地址:http://blog.jobbole.com/18587/ 【译注】:圣经记载:在远古的时候,人类都使用一种语言,全世界的人决定...

    智能算法
  • 亚马逊工程师论各种编程语言的优缺点

    我是攻城师
  • 几种编程语言的优缺点

    我的旋风式简介会讲C、C++、Lisp、Java、Perl 、Ruby (我就是喜欢) 和 Python,把 Python 加进来是因为 —— 好吧,你看了就知...

    量化投资与机器学习微信公众号
  • 我是如何通过开源项目月入 10 万的?

    如果你是一名前端工程师或者像我一样的全站工程师,那么一定对 fullPage.js 这个开源项目不会感到陌生。这是前端社区中非常著名的 JavaScript 组...

    沉默王二
  • 我是如何通过开源项目月入 10 万的?

    如果你是一名前端工程师,那么你一定对 fullPage.js 这个开源项目不会感到陌生。这是前端社区中非常著名的 JavaScript 组件,能快速给网站加上全...

    开源社
  • 我是如何通过开源项目月入 10 万的?

    如果你是一名前端工程师,那么你一定对 fullPage.js 这个开源项目不会感到陌生。这是前端社区中非常著名的 JavaScript 组件,能快速给网站加上全...

    GitHubDaily

扫码关注云+社区

领取腾讯云代金券