1818Given n will always be valid.
1919Try to do this in one pass.*/
2020public class RemoveNthNodeFromEndOfList {
21- public ListNode removeNthFromEnd (ListNode head ,int n ) {
21+
22+ /**Naive/most straightforward approach:
23+ * go through the list, find its total length, then go through the list a second time:
24+ * this time, pause at the delta point, then assign its next.next pointer to next.
25+ * This approach has to traverse the list twice, not one-pass.*/
26+ public ListNode removeNthFromEnd_two_passes (ListNode head ,int n ) {
2227ListNode temp =head ;
2328int len =0 ;
2429while (temp !=null ){
@@ -40,10 +45,58 @@ public ListNode removeNthFromEnd(ListNode head, int n) {
4045 }
4146
4247public static void main (String ...strings ){
48+ int n =2 ;
4349ListNode head =new ListNode (1 );
4450head .next =new ListNode (2 );
4551RemoveNthNodeFromEndOfList test =new RemoveNthNodeFromEndOfList ();
46- ListNode res =test .removeNthFromEnd (head ,2 );
52+ // ListNode res = test.removeNthFromEnd_two_passes(head, n);
53+ ListNode res =test .removeNthFromEnd_one_pass (head ,n );
4754CommonUtils .printList (res );
4855 }
56+
57+ public ListNode removeNthFromEnd_one_pass (ListNode head ,int n ) {
58+ //this approach uses two pointers, fast moves first for n nodes, when fast reaches n, then we start to move slow
59+ //then, when fast reaches null, slow reaches the point where the node should be deleted.
60+ ListNode dummy =new ListNode (-1 );
61+ dummy .next =head ;
62+ ListNode slow =head ,fast =head ;
63+ int tempN =n ;
64+ while (tempN -- >0 ){
65+ fast =fast .next ;
66+ }
67+
68+ if (fast ==null ) {
69+ if (n >0 ) {
70+ // this is for cases like this: [1,2] 2 or [1,2,3,4] 4, namely, remove the head of
71+ // the list and return the second node from the original list
72+ dummy .next =dummy .next .next ;
73+ }
74+ return dummy .next ;
75+ }
76+
77+ fast =fast .next ;//we'll have to move fast pointer one node forward before moving the two together, this way,
78+ //when fast reaches null, slow will be at the previous node to the node that should be deleted, thus, we can change the next pointer easily
79+
80+ while (fast !=null ){
81+ fast =fast .next ;
82+ slow =slow .next ;
83+ }
84+
85+ if (slow .next !=null )slow .next =slow .next .next ;
86+ return dummy .next ;
87+ }
88+
89+ //a more concise version using the same idea found on Discuss
90+ public ListNode removeNthFromEnd_one_pass_more_concise_version (ListNode head ,int n ) {
91+ ListNode dummy =new ListNode (-1 );
92+ dummy .next =head ;
93+ ListNode slow =dummy ,fast =dummy ;
94+ while (fast .next !=null ){
95+ if (n <=0 )slow =slow .next ;
96+ fast =fast .next ;
97+ n --;
98+ }
99+ if (slow .next !=null )slow .next =slow .next .next ;
100+ return dummy .next ;
101+ }
49102}