-
Notifications
You must be signed in to change notification settings - Fork 0
/
RemoveNthNodeFromList.java
101 lines (71 loc) · 2.65 KB
/
RemoveNthNodeFromList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
public class RemoveNthNodeFromList {
// 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; }
}
//My solution:
//First I iterated through the complete linked list and got the full length, then I
//got the index of the node I'm supposed to remove then I did the magic
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode currentNode = head;
int numberOfNodes = 1;
while(currentNode.next != null){
numberOfNodes++;
currentNode = currentNode.next;
}
System.out.println("Number of nodes: " + numberOfNodes);
int nodeAt = numberOfNodes - n;
int counter = 0;
currentNode = head;
ListNode nodeBefore = head;
ListNode nodeAfter = null;
while(counter < numberOfNodes){
if(counter == (nodeAt - 1)){
nodeBefore = currentNode;
System.out.println("Node before: "+ nodeBefore.val);
}
if(counter == (nodeAt + 1)){
nodeAfter = currentNode;
System.out.println("Node after: "+ nodeAfter.val);
}
currentNode = currentNode.next;
counter++;
}
if(nodeAt == 0 ){
if(nodeAfter != null){
return nodeAfter;
}
return null;
}
nodeBefore.next = null;
if(nodeAfter != null){
nodeBefore.next = nodeAfter;
}
return head;
}
//Optimal Solution
//We using two pointer nodes to solve this problem. One fast node is sent far into the future using the first
//for loop, then we keep itering until the fast loop is null, at that point the slow pointer should be just behing the
//node we're supposed to remove.
//then we execute slow.next = slow.next.next
public ListNode removeNthFromEndOptimal(ListNode head, int n){
//0 [1,2,3,4,5,6,7,8,9], n = 3
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode slow = dummyHead;
ListNode fast = dummyHead;
for(int i = 1; i <= n + 1; i++){
fast = fast.next;
}
while(fast != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
}