每周算法:删去单向链表倒数第n个节点

leetcode算法题第19道,难度为medium,考察链表的基本操作。

Description

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

Example:

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.

来源:leetcode 19 remove nth node from end of list

Solution

Approach 1 Reverse List

这道题是比较基础的一道题,我的思路是将链表翻转,这样就将题目转换为删去正数第n个元素。但是这种方法需要将链表翻转两次,所以从效率上来讲并不好,而且需要注意的边界条件还挺多,在这里仅作为参考思路。

ListNode* reverseList(ListNode* head) {
    ListNode* temp1 = head;
    ListNode* temp2 = head->next;
    while (temp2) {
	ListNode* t = temp2->next;
	temp2->next = temp1;
	temp1 = temp2;
	temp2 = t;
    }
    head->next = NULL;
    return temp1;
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (head == NULL) {
	return NULL;
    }
    // 删去最后一个
    if (n==1) {
	if (head->next == NULL) {
	    return NULL;
	}
	ListNode* temp = head;
	while (temp->next) {
	    if (temp->next->next == NULL) {
		temp->next = NULL;
		break;
	    }
	    temp = temp->next;
	}
	return head;
    }
    // 翻转链表
    ListNode* temp1 = reverseList(head);
    // 找到需要删除的倒数第n个结点
    ListNode* temp3 = temp1;
    for (int i=2; i<n; ++i) {
	temp3 = temp3->next;
    }
    // temp3 此时是需要删除的节点的前一个节点
    // 如果删去的是头结点
    if (temp3->next == head) {
	temp3->next = NULL;
    }
    else {
	temp3->next = temp3->next->next;
    }
    // 关于内存释放问题,由于不知道内存是如何申请的(malloc,new),所以不能轻易释放
    // 此时节点删除完成
    return reverseList(temp1);
}

Approach 2 Two pass algorithm

这个解法是在leetcode的solution解析中看到的,解法的意图是将问题转化为删去正数第 l-n+1 个节点。其中 l 为链表的长度,这个是容易获得的。

下面是我按照这种思想使用C++进行编写的解法:

ListNode* removeNthFromEnd(ListNode* head, int n) {
    // 第一次遍历,得到链表长度
    int len = 0;
    ListNode* p1 = head;
    while (p1) {
	p1 = p1->next;
	++len;
    }

    // 删除正数第1个节点
    if (n == len) {
	ListNode* p = head->next;
	delete head;
	return p;
    }

    // 需要找到第 len - n 个节点(删除节点的前一个节点)
    ListNode* p2 = head;
    for (int i=0; i<len-n-1; ++i) {
	p2 = p2->next;
    }
    ListNode* p3 = p2->next;
    p2->next = p3->next;
    delete p3;
    p3 = nullptr;

    return head;
}

我在完成这个解法时,发现在删去正数第 l-n+1 个节点时,需要找到的实际上是正数第 l-n 个节点。这样,如果要删去正数第1个节点时,就需要对这个边界条件进行特殊处理。

使用一个 dummy 节点,将头节点包裹起来,就解决了之前的边界问题。 在遇到边界条件时,尝试将边界包裹起来,这样边界就转换为非边界了。 下面的实现代码截取自leetcode,使用java编写。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int length  = 0;
    ListNode first = head;
    while (first != null) {
	length++;
	first = first.next;
    }
    length -= n;
    first = dummy;
    while (length > 0) {
	length--;
	first = first.next;
    }
    first.next = first.next.next;
    return dummy.next;
}

这种算法的时间复杂为 O(l) ,第一次遍历求链表长度,第二次遍历找第 l-n 个节点,一共有 2L-n 次操作。空间复杂度为 O(1) ,没有使用额外的空间。

Approach 3 One pass algorithm

上面的解法能够优化为使用一轮循环。需要使用两个指针,第一个指针指向第 n+1 个节点,第二个指针指向第一个节点,这样两个指针就间隔 n 个节点了。同时将两个节点后移,在第一个指针到达尾部时,第二个指针所指的下一个节点就是需要删除的节点。
下面就是实现代码,截取自leetcode,使用java编写。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer
    // so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
	first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
	first = first.next;
	second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

这种算法的时间复杂为 O(l) ,它对链表进行了一次全遍历。空间复杂度为 O(1) ,没有使用额外的空间。

Extras

现在所有的方法都介绍到了,很明显,第三种方法的效率是最高的(操作次数最少)。这是在题目限定 n 一定有合理取值的情况下。如果 n 的取值有可能无效呢?这时就需要在每次指针操作时加以判断。再者,需要制定 n 取值无效时的策略,在取值无效时放弃本次删除操作,也可以删去与 n 距离最接近的节点。 n 的取值可能过小或过大。在 n 过小时(负数或0),可将 n 设定为1,这种情况对以上三种解法的影响是相同的。在 n 过大时,可以将 n 设定为 l ,这样第三种解法效率优势就会丢失,第一种和第二种解法受到的影响相对较小。

Comments

Comments powered by Disqus