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

灰子学技术

发布于 2020-07-27 23:08:55

5140

发布于 2020-07-27 23:08:55

文章被收录于专栏：灰子学技术

算法：

该类型的题目，核心点在于如何找到倒数第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
}

执行结果：