當前位置:網站首頁>19. 删除鏈錶的倒數第 N 個結點

19. 删除鏈錶的倒數第 N 個結點

2022-05-13 23:07:21知識學徒

LeetCode原題鏈接

明確題意


删除鏈錶節點的問題。

删除方式:删除節點的是找到該結點的上一個結點node:node.next = node.next.next;

那麼題目中要删除倒數第N個結點就意味著,我們找到倒數第N+1個結點比特置即可。

解法

在單鏈錶找到倒數第N的結點的方法可以是:

先找到正序第N個結點,兩個指針分別指向頭結點和第N個結點,循環直至第N個結點的next為null,head指向的即是倒數第N+1個結點比特置。

Coding

通過題意直接在本地通過TDD(測試驅動開發)的方式寫算法題。

首先編寫測試用例如下:

package tdd.algo;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNull;
import static xqb.tdd.algo.ListNodeHandler.removeNthFromEnd;

class RemoveNthFromEndTest {
    
  /** head = [1,2,3,4,5], n = 2 輸出:[1,2,3,5] */
  @Test
   void should_remove_nth_from_the_last_of_list() {
    
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        int n = 2;

        ListNode node = removeNthFromEnd(head, n);
        assertEquals(1, node.val);
        assertEquals(2, node.next.val);
        assertEquals(3, node.next.next.val);
        assertEquals(5, node.next.next.next.val);
  }

    @Test
    void should_remove_nth_from_single_value_list() {
    
        ListNode head = new ListNode(1);
        int n = 1;

        ListNode node = removeNthFromEnd(head, n);
        assertNull(node);
    }
}

再編寫代碼逐個通過測試:


    public static ListNode removeNthFromEnd(ListNode head, int n) {
    
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode index = head;
        while(n-- > 0){
    
            index = index.next;
        }

        ListNode pre = dummy;
        while(index != null){
    
            pre = pre.next;
            index = index.next;
        }

        pre.next = pre.next.next;
        return dummy.next;
    }

TestCases

要想熟悉算法題,刷一遍肯定不是够的。
當有了測試保障功能的實現時,保留測試後可以放心删除代碼,重新實現以提高熟練度。

最好將刷題代碼進行版本控制,如果之後想不起來可以 git reset --hard

需要注意下面的代碼差异:

版權聲明
本文為[知識學徒]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/133/202205132255095271.html

隨機推薦