一道编程题——删除倒数第k个节点

题目描述

给定一个链表，删除链表的倒数第n个节点并返回链表的头指针，给出的链表为:1->2->3->4->5, n= 2。 删除了链表的倒数第n个节点之后,链表变为1->2->3->5。（保证n为有效值）

删除一个节点，可以找出其前一个节点，然后将其next指针指向需要删除的节点的后一个节点。或者也可以找到要删除的节点，将其数据域设置为其后一个节点的值，然后next指针指向要删除的节点的后两个节点。

代码实现

python实现

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def removeNthFromEnd(self , head , n ):
        # write code here
        if (not head): return None
        # 找到倒数第n个节点的前一个节点，也就是倒数第n+1个节点
        node = self.findNthNode(head, n+1)
        if node:
            node.next = node.next.next
        else:
            head = head.next
        return head
    
    # 寻找倒数第n个节点，不存在则返回None
    def findNthNode(self, head, n):
        firstP, secondP = head, head
        while(firstP and n):
            n-=1
            firstP = firstP.next
        # fristP指针刚好不存在，而n已经等于0，也就是说倒数第n个正好是头节点
        if (not firstP and n==0):
            return head
        # firstP不存在且不足n个节点，则说明没有倒数第n个节点
        elif(not firstP):
            return None 
        while(firstP):
            firstP  =firstP.next
            secondP = secondP.next
        return secondP

C++实现

由于本题说明n为有效值，则可以稍微简单一点，不考虑n大于链表长度的情况：

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        ListNode* fast = head;
        ListNode* slow = head;
        if(head==NULL)return NULL;
        while(n>0 && fast!=NULL){
            fast = fast->next;
            n-=1;
        }
        // 要删除的为head节点，即链表长度为n
        if(fast==NULL)return head->next;
        // 链表长度小于n
        while(fast->next!=NULL){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};