【LeetCode】19. Remove Nth Node From End of List 解答・解説【Python】

学習メモ。

自分の言葉で書くことで理解できていない部分をはっきりさせる。

問題
1. 原文
2. 内容
解答
1. 解答1：Python,　two pointer
2. 解答2：Rust
補足・参考・感想

問題

原文

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

Example 1:

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

1
2

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1 Output: []

1
2

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1 Output: [1]

1
2

Input: head = [1,2], n = 1
Output: [1]

Constraints:

The number of nodes in the list is sz.

1 <= sz <= 30

0 <= Node.val <= 100

1 <= n <= sz

Follow up: Could you do this in one pass?

内容

連結リストheadが与えられます。連結リストの後ろからn番目のノード(要素)を削除し、headを返してください。

※正しくない可能性があります。

解答

解答1：Python,　two pointer

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        #fast,slowにheadの先頭要素を代入
        fast = slow = head

        #fastの連結リストをn回進める
        for _ in range(n):
            #fastを連結リストの次の要素へ進める
            fast = fast.next

        #fastがNoneの時　※fastが連結リストの最後まで到達した場合の処理
        #head=[1],n=1や、head=[1,2,3],n=3など連結リストの要素数とnの数が一致している場合、
        if not fast:
            #n回連結リストを進めると最後の要素に到達(fastがNoneになる)するので、
            #headの2つ目の要素以降を返すことが解答になる。
            return head.next
        #n回fastを進めた後から、fastとslowを同時に進めていく
        while fast.next:
            #fastとslowを進める
            fast = fast.next
            slow = slow.next
        #削除操作　※slow.nextにslow.nextではなく、slow.next.nextへリンクする
        slow.next = slow.next.next
        return head

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, val=0, next=None):

# self.val = val

# self.next = next

class Solution:

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:

#fast,slowにheadの先頭要素を代入

fast = slow = head

#fastの連結リストをn回進める

for _ in range(n):

#fastを連結リストの次の要素へ進める

fast = fast.next

#fastがNoneの時　※fastが連結リストの最後まで到達した場合の処理

#head=[1],n=1や、head=[1,2,3],n=3など連結リストの要素数とnの数が一致している場合、

if not fast:

#n回連結リストを進めると最後の要素に到達(fastがNoneになる)するので、

#headの2つ目の要素以降を返すことが解答になる。

return head.next

#n回fastを進めた後から、fastとslowを同時に進めていく

while fast.next:

#fastとslowを進める

fast = fast.next

slow = slow.next

#削除操作　※slow.nextにslow.nextではなく、slow.next.nextへリンクする

slow.next = slow.next.next

return head

・連結リストの削除操作について

連結リストは、ある要素から次の要素へ数珠つなぎのように指してつながっている。

削除操作をする場合はPythonのリストのように要素を消すのではなく、今の要素から次の次の要素を指すことで、次の要素を削除することができる

・for節について　※なぜ最初にn回fastを進めるのか。

Pythonのリストであれば、添字で後ろからn番目の要素を指して削除できるが、

単方向連結リストでは、(たぶん)前から後ろにしか進むことができないので、

削除対象を前から数える必要がある。

連結リストで前から何番目の要素であるかを指すためにfast,slowの2つのポインタを使うが、

先にfastをn回進めて置き、

その後でfastの残りの要素分、fastとslowを同時に進めると、(while節の操作)

削除対象の要素がslow.nextになる。

・if節について

for節の実行で、最後の要素まで到達してしまう場合がある。

head = [1], n=1、　head=[1,2,3,4,5], n = 5のように要素数とnの数が一致する場合を指す。

これは、後ろからn番目、つまり先頭の要素を削除すると良い。

head= [1,2,3], n = 6のように要素数を超えるnの数は、要素がなくなってしまうので問題の制約としてこの事例は起こらないようにされている。

・テストケース3：head=[1,2],n=1の場合

for節の実行終了後、fastの中身は[value:2, next=None]となり、連結リストの最後まで到達している。

while文では、fast.nextがNoneでない限り処理を行うが、fast.nextはNoneのため、while節は実行されない

slowはheadの先頭要素を指しているが、2つ目の要素かつ最後の要素である2の削除操作をすることになる。

解答2：Rust

// 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 = ListNode::new(0);
        dummy.next = head;
        let mut dummy = Box::new(dummy);
        let mut fast = dummy.clone();
        let mut slow = dummy.as_mut();

        for _ in 0..n {
            fast = fast.next.unwrap();
        }

        while fast.next.is_some() {
            fast = fast.next.unwrap();
            slow = slow.next.as_mut().unwrap();
        }
        
        let next = slow.next.as_mut().unwrap();
        slow.next = next.next.clone();
        dummy.next
    }
}

// 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 = ListNode::new(0);

dummy.next = head;

let mut dummy = Box::new(dummy);

let mut fast = dummy.clone();

let mut slow = dummy.as_mut();

for _ in 0..n {

fast = fast.next.unwrap();

}

while fast.next.is_some() {

fast = fast.next.unwrap();

slow = slow.next.as_mut().unwrap();

}

let next = slow.next.as_mut().unwrap();

slow.next = next.next.clone();

dummy.next

}

写経

補足・参考・感想

■補足

■参考

■感想

1回目に見たときは理解できなかったので写経だけやって無視してた問題。

問題の前提を確認しつつ、いくつかの解答案と良し悪し説明する。しかも英語でコミュニケーションして、10分くらいでホワイトボードにコードを書けるようにならないとダメと考えると、この問題の解き方を1つ知っただけだと必要な準備の1割も達成できていない。

前：344. Reverse String

次：567. Permutation in String

LeetCode 解答・解説記事一覧

問題

原文

内容

解答

解答1：Python, two pointer

解答2：Rust

補足・参考・感想

コメント

解答1：Python,　two pointer