leetcode-19-Remove-Nth-Node-From-End-of-List

发表于   |  

描述

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

For example,

1
2
3
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.

分析

设置3个指针，其中两指针间相隔的元素是n-1个，当第二个指针指向链尾元素时，此时第一个指针指向的元素即要移除的元素，利用第一个指针前的一个指针将该指针移除，要注意边界情况，比如要移除的元素是链表的第一个元素。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == NULL) {
            return NULL;
        }
        
        ListNode *first_pre = NULL;
        ListNode *first = head;
        ListNode *second = head;
        
        for(int i = 0; i < n-1; i++){
            second = second->next;
        }
        while(second->next) {
            first_pre = first;
            first = first->next;
            second = second->next;
        }
        if(first_pre == NULL) {
            head = first->next;
            delete first;
        }else {
            first_pre->next = first->next;
            delete first;
        }
        return head;
    }
};

解决方案2(Rust)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
// 
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy_head = Some(Box::new(ListNode {val: 0, next: head }));
        let mut len = 0;
        {
            let mut now = dummy_head.as_ref();
            while now.unwrap().next.is_some() {
                len += 1;
                now = now.unwrap().next.as_ref();
            }
        }
        
        let idx = len - n;
        {
            let mut now = dummy_head.as_mut();
            for _ in 0..(idx) {
                now = now.unwrap().next.as_mut();
            }
            let next = now.as_mut().unwrap().next.as_mut().unwrap().next.take();
            now.as_mut().unwrap().next = next;
        }
        dummy_head.unwrap().next
    }
}

解决方案3（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    length := getLength(head)
    dummy := &ListNode{0, head}
    current := dummy
    for i := 0; i < length-n; i++ {
        current = current.Next
    }
    current.Next = current.Next.Next
    return dummy.Next
}

func getLength(head *ListNode) (length int) {
    for ; head != nil ; head = head.Next {
        length++
    }
    return
}

相关问题

题目来源