# 19 Remove Nth Node From End of List

Remove Nth Node From End of List Go to Discuss

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.

Follow up:

Could you do this in one pass?

題目敘述:

這是給一個linked list ，再給一個位置(要刪掉的位置)，但是從後面數過來。

解題思路:

1 先取linked list的長度

Get linked list length

2 假設給的位置是n，那前一位就是leng - n ==> leng == n + (leng - n)

Suppose remove n-th node is "n",the before node location is "length - n"

3 找到前一個node後，再指定node.next = 原linked list的next.next

Fine before node, let assignment beforeNode.next = Original Linked list.next.next

4 要注意是位置可能會給負的、零，零或負的話就是刪掉第一個元素。

Notice : the remove n-th maybe is nagative or zero, if n is zero/nagative, just remove original linked list first element.

這裡說明一下，若原長度是[1,2,3], 刪的位置是 超過3也就是 4，5…

This illustrate , if original linked list is [1,2,3], the remove n-th over 3 , just like 4, 5...

3 - 4 = -1, this queention let remove first element in origianl linked list, so use if(count <= 0) condition to check count (this count = length - n)

3 - 4 = -1 ，以該題結果是要刪掉第一個元素，所以有用if(count <= 0) 來判斷。

程式碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(n < 0 || head == null){
            return head;
        }
        //step 2 get length
        ListNode node = head;
        int leng = 0;
        while(node != null){
            node = node.next;
            leng++;
        }
        // System.out.println("leng = " + leng);
        
        //step 3 combine nodeNew
         
        int count = leng - n;
        int test = 0;
        node = head;
        ListNode nodeNew;
        ListNode tempNode;
         // System.out.println("count = " + count);
        if(count <= 0){
            nodeNew = head.next;
            return nodeNew;
        }
         nodeNew = new ListNode(node.val);
        for(int i = 1; i< leng ; i++){
            if(i == count){
                // if(count == 0){
                    // node = node.next;
                // }else{
                node = node.next.next;
                // }
                tempNode = nodeNew;
                while(tempNode.next != null){
                    tempNode = tempNode.next;
                }
                tempNode.next = node;
                // nodeNew = tempNode;
                //  ListNode p= nodeNew;
                // while(p != null){
                //  System.out.println("if loop p.val = " + p.val);
                //     p = p.next;
                // }
                //  System.out.println("if loop i = " + i + "\n");
                
                break;    
            }
            node = node.next;
            tempNode = nodeNew;
            while(tempNode.next != null){
                tempNode = tempNode.next;
            }
            tempNode.next = new ListNode(node.val);
            // nodeNew = tempNode;
            // ListNode p= nodeNew;
            //  while(p != null){
            //     System.out.println("p.val = " + p.val);
            //     p = p.next;
            // }
            // System.out.println("i = " + i + "\n");
            
        }
        // node.next = node.next.next;
        ListNode print = nodeNew;
        //setp 4 print 
        while(print != null){
            System.out.println("print.val = " + print.val);
            print = print.next;
        }
        return nodeNew;
        
    }
}

另一個解題思路: 是用2個pointer去

2個point 一開始都是參考head，但nextNode多走一步。preNode就是前一步。找到要刪掉的n-th位置的前一個位置也是pre，pre.next本來是指要刪掉的n-th元素，現在pre.next = nextNode.next

舉例:

[1,2,3,4,5]

2

size = 5, count = 5-2 =3

c: 0 , pre = 12345, next = 2345, c++

c:1, pre = 2345,next = 345 ,c++

c:2 ,pre = 345,next = 45 ,c++

c:3 不小於 3跳出while loop

pre = 345 , pre.next = 4 ; next = 45, next.next = 5

現在j把pre.next改指定到next.next, 原本指到4改指到5。

然後回傳head即可。

這裡也是有判斷pre = null，也就是當size - n =0 或是 size - n = 負數 。那就不會進while 迴圈了，所以pre == null , 也就回傳head.next(刪掉head 第一個元素即可)

程式碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = head;
        ListNode preNode = null;
        ListNode nextNode = head;
        
        int length = 0;
        int count = 0;
        while(temp != null){
            temp = temp.next;
            length++;
        }
        
        while(count < length - n){
            preNode = nextNode;
            nextNode = nextNode.next;
            count++;
        }
        if(preNode == null){
            return head.next;
        }
        preNode.next = nextNode.next;
        
//         //print
//         temp = head;
//         while(temp != null){
//             System.out.println("temp.val = " + temp.val);
//             temp = temp.next;
//         }
//         //print
        return head;
    }
}