leetcode19-删除連結清單的倒數第N個節點

• ​​删除連結清單的倒數第N個節點​​

• ​​題目描述​​
• ​​code​​

• ​​官方答案​​

删除連結清單的倒數第N個節點

題目描述

給定一個連結清單，删除連結清單的倒數第 n 個節點，并且傳回連結清單的頭結點。

示例：

給定一個連結清單: 1->2->3->4->5, 和 n = 2.

當删除了倒數第二個節點後，連結清單變為 1->2->3->5.
說明：      

code

import org.junit.Test;
import java.util.List;

/**
 * 給定一個連結清單，删除連結清單的倒數第 n 個節點，并且傳回連結清單的頭結點。
 * <p>
 * 示例：
 * <p>
 * 給定一個連結清單: 1->2->3->4->5, 和 n = 2.
 * <p>
 * 當删除了倒數第二個節點後，連結清單變為 1->2->3->5.
 * 說明：
 * <p>
 * 給定的 n 保證是有效的。
 * <p>
 * 進階：
 * 你能嘗試使用一趟掃描實作嗎？
 */
public class LeetCode19 {
    @Test
    public void test() {
        Solution s = new Solution();
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
        ListNode node = s.removeNthFromEnd(head, 2);

        while(node!= null){
            System.out.println(node.val);
            node= node.next;
        }
    }


    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    //删除倒數的第n個節點，并傳回頭結點
    //思路： 雙指針，先走n步，然後兩個指針同時走，還需要一個指針，進行連接配接
    //為空/ 超過 / 正常 /頭結點/ 非頭結點
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if (head == null) return null;

            ListNode tmpHead = new ListNode(-1);
            tmpHead.next = head;
            ListNode cur = head;
            ListNode prev = tmpHead;
            while (n-- > 0) {
                cur = cur.next;
                if (cur == null ) {
                    //走到末尾   1->2
                    if( n>0){
                        return null;
                    }else if(n==0){
                          tmpHead.next = tmpHead.next.next;
                          return tmpHead.next;
                    }
                }
            }
            //如果删除的節點是頭結點 /非頭結點
            while (cur != null && prev != null) {
                prev = prev.next;
                cur = cur.next;
            }
            ListNode next = prev.next;
            if(next != null){
                prev.next = next.next;
            }else{
                prev.next = null;
            }
            return tmpHead.next;
        }
    }
}
      

官方答案

public ListNode removeNthFromEnd2(ListNode head, int n) {
            ListNode dummy = new ListNode(0); //建立一個假頭
            dummy.next = head;  //假頭指向頭結點
            ListNode first = dummy; //快指針first
            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; //
            }
            //快慢指針同時進行移動
            while (first != null) {
                first = first.next;
                second = second.next;
            }
            //慢指針跳過這個要删除的節點
            second.next = second.next.next;
            return dummy.next;
}