Linked List - Remove Nth Node From End of List

by LauCyun Sep 20,2014 13:46:17 3,557 views

Question

Problem Statement

Given a linked list, remove the nth node from the end of list and return its head.

  •  Notice
    The minimum number of nodes in list is n.

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.

题解

简单题, 使用快慢指针解决此题,需要注意最后删除的是否为头节点。让快指针先走n步,直至快指针走到终点,找到需要删除节点之前的一个节点,改变slow->next域即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * Remove Nth Node From End of List.
 *
 * @param head: The first node of linked list.
 * @param n: An integer.
 * @return: The head of linked list.
 */
struct ListNode *
removeNthFromEnd(struct ListNode *head, const int n) {
    if (head == NULL || n < 0) {
        return NULL;
    }

    struct ListNode *fast = head;
    struct ListNode *slow = head;

    int i = 0;
    while (i < n) {
        if (fast == NULL) {
            return NULL;
        }
        fast = fast->next;
        ++i;
    }
    if (fast == NULL) {
        return head->next;
    }

    while (fast->next != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    slow->next = slow->next->next;
    return head;
}

以上代码单独判断了是否需要删除头节点的情况,在遇到头节点不确定的情况下,引入dummy节点将会使代码更加优雅,改进的代码如下。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * Remove Nth Node From End of List.
 *
 * @param head: The first node of linked list.
 * @param n: An integer.
 * @return: The head of linked list.
 */
struct ListNode *
removeNthFromEnd(struct ListNode *head, const int n) {
    if (head == NULL || n < 0) {
        return NULL;
    }

    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = -1;
    dummy->next = head;
    struct ListNode *curr = dummy;

    int i = 0;
    while (i < n) {
        if (head == NULL) {
            return NULL;
        }
        head = head->next;
        ++i;
    }

    while (head != NULL) {
        head = head->next;
        curr = curr->next;
    }

    curr->next = curr->next->next;
    head = dummy->next;
    free(dummy);
    return head;
}

Tags