LeetCode - Remove Nth Node From End of List

Problem link : https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/603/

Explore - LeetCode

 

When we write code for adding or removing node, we have to distinguish and differently write codes depending on whether the target node is first node or not. For example, If you want to remove second node, you should connect first node and third node. After then, you can remove second node.

However, If you want to remove first node, you don't need to connect anything. you just move your head and remove first node. That's all.

 

Now, we are clear what should we do to. And you will go to write some code.

But It is not good code. The change removing first node is so rare case. But we have to write code two time just for first node. it is not so efficient.

We can only one code and apply same logic to every node, if we add a dummy node in front of first node. The dummy node is fake first node.

Linus Torvalds talked about this data structure in TED. 

 

 

 

 

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1, head);
        
        ListNode* cur = dummy;
        
        int listSize = 0;
        
        while (cur != nullptr) {
            cur = cur->next;
            listSize++;
        }

        int target = listSize - n - 1;
        cur = dummy;
        for (int i = 0; i < target; i++) {
            cur = cur->next;
        }
        
        ListNode* temp = cur->next;
        cur->next = cur->next->next;
                
        head = dummy->next;
        delete temp;
        delete dummy;
        
        return head;
    }
};

 

 

 

 

 

 

JAVA

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        
        int listSize = 0;
        
        while (cur != null) {
            cur = cur.next;
            listSize++;
        }
        
        int target = listSize - n - 1;
        cur = dummy;
        for (int i = 0; i < target; i++) {
            cur = cur.next;
        }
        
        ListNode temp = cur.next;
        cur.next = cur.next.next;
        
        head = dummy.next;
        
        return head;   
    }
}

 

 

 

 

 

 

Python3

# 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]:
        dummy = ListNode(-1, head)
        cur = dummy
        
        list_size = 0
        
        while cur is not None:
            cur = cur.next
            list_size += 1
        
        target = list_size - n - 1
        cur = dummy
        for i in range(target):
            cur = cur.next
        
        temp = cur.next
        cur.next = cur.next.next
        
        head = dummy.next
        
        return head

 

 

 

If you want to any question, please leave a comment.