Given a linked list, remove the nth node from the end of list and return its head.
For 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.
Try to do this in one pass.
This article is for beginners. It introduces the following idea:\nLinked List traversal and removal of nth element from the end.
\nIntuition
\nWe notice that the problem could be simply reduced to another one : Remove the th node from the beginning in the list , where is the list length. This problem is easy to solve once we found list length .
\nAlgorithm
\nFirst we will add an auxiliary "dummy" node, which points to the list head. The "dummy" node is used to simplify some corner cases such as a list with only one node, or removing the head of the list. On the first pass, we find the list length . Then we set a pointer to the dummy node and start to move it through the list till it comes to the th node. We relink next
pointer of the th node to the th node and we are done.
Figure 1. Remove the L - n + 1 th element from a list.
\nJava
\npublic ListNode removeNthFromEnd(ListNode head, int n) {\n ListNode dummy = new ListNode(0);\n dummy.next = head;\n int length = 0;\n ListNode first = head;\n while (first != null) {\n length++;\n first = first.next;\n }\n length -= n;\n first = dummy;\n while (length > 0) {\n length--;\n first = first.next;\n }\n first.next = first.next.next;\n return dummy.next;\n}\n
Complexity Analysis
\nThe algorithm makes two traversal of the list, first to calculate list length and second to find the th node. There are operations and time complexity is .
\nAlgorithm
\nThe above algorithm could be optimized to one pass. Instead of one pointer, we could use two pointers. The first pointer advances the list by steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the th node counting from the last.\nWe relink the next pointer of the node referenced by the second pointer to point to the node\'s next next node.
\nFigure 2. Remove the nth element from end of a list.
\nJava
\npublic ListNode removeNthFromEnd(ListNode head, int n) {\n ListNode dummy = new ListNode(0);\n dummy.next = head;\n ListNode first = dummy;\n ListNode second = dummy;\n // Advances first pointer so that the gap between first and second is n nodes apart\n for (int i = 1; i <= n + 1; i++) {\n first = first.next;\n }\n // Move first to the end, maintaining the gap\n while (first != null) {\n first = first.next;\n second = second.next;\n }\n second.next = second.next.next;\n return dummy.next;\n}\n
Complexity Analysis
\nTime complexity : . The algorithm makes one traversal of the list of nodes. Therefore time complexity is .
\nSpace complexity : .\nWe only used constant extra space.
\nAnalysis written by: @elmirap.
\n