{"action":"created","issue":{"url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/53","repository_url":"https://api.github.com/repos/cbweixin/algorithm-practice","labels_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/53/labels{/name}","comments_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/53/comments","events_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/53/events","html_url":"https://github.com/cbweixin/algorithm-practice/issues/53","id":114715777,"number":53,"title":"Remove Nth node from end of list","user":{"login":"cbweixin","id":1326906,"avatar_url":"https://avatars.githubusercontent.com/u/1326906?v=3","gravatar_id":"","url":"https://api.github.com/users/cbweixin","html_url":"https://github.com/cbweixin","followers_url":"https://api.github.com/users/cbweixin/followers","following_url":"https://api.github.com/users/cbweixin/following{/other_user}","gists_url":"https://api.github.com/users/cbweixin/gists{/gist_id}","starred_url":"https://api.github.com/users/cbweixin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cbweixin/subscriptions","organizations_url":"https://api.github.com/users/cbweixin/orgs","repos_url":"https://api.github.com/users/cbweixin/repos","events_url":"https://api.github.com/users/cbweixin/events{/privacy}","received_events_url":"https://api.github.com/users/cbweixin/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-11-03T00:28:12Z","updated_at":"2016-03-09T19:14:45Z","closed_at":null,"body":"### Problem\r\nGiven a linked list, remove the nth node from the end of list and return its head.\r\n\r\nFor example,\r\n\r\n      Given linked list: 1->2->3->4->5, and n = 2.\r\n\r\n      After removing the second node from the end, the linked list becomes 1->2->3->5.\r\n\r\nNote:\r\nGiven n will always be valid.\r\nTry to do this in one pass. \r\n\r\n### Attempt 1\r\n```c++\r\n/**\r\n * Definition for singly-linked list.\r\n * struct ListNode {\r\n *     int val;\r\n *     ListNode *next;\r\n *     ListNode(int x) : val(x), next(NULL) {}\r\n * };\r\n */\r\nclass Solution {\r\npublic:\r\n    ListNode* removeNthFromEnd(ListNode* head, int n) {\r\n        \r\n        if(head==NULL){\r\n            return NULL;\r\n        }\r\n        if(head->next==NULL && n==1){\r\n            return NULL;\r\n        }\r\n        \r\n        ListNode *a = head;\r\n        ListNode *b = head;\r\n        while(n>0){\r\n            a = a->next;\r\n        }\r\n        while(a->next!=NULL){\r\n            a = a->next;\r\n            b = b->next;\r\n        }\r\n        \r\n        b->next = b->next->next;\r\n        \r\n        return head;\r\n        \r\n    }\r\n};\r\n```\r\n\r\n#### result \r\n![image](https://cloud.githubusercontent.com/assets/1326906/10898395/dd638e8a-817e-11e5-8e78-4397392adf4c.png)\r\n\r\n#### Analysis\r\n\r\n       while(n>0){\r\n            a = a->next;\r\n        }\r\n\r\nstupid mistake, infinite loop.\r\n\r\n### Attempt 2\r\n```c++\r\n/**\r\n * Definition for singly-linked list.\r\n * struct ListNode {\r\n *     int val;\r\n *     ListNode *next;\r\n *     ListNode(int x) : val(x), next(NULL) {}\r\n * };\r\n */\r\nclass Solution {\r\npublic:\r\n    ListNode* removeNthFromEnd(ListNode* head, int n) {\r\n        \r\n        if(head==NULL){\r\n            return NULL;\r\n        }\r\n        if(head->next==NULL && n==1){\r\n            return NULL;\r\n        }\r\n        \r\n        ListNode *a = head;\r\n        ListNode *b = head;\r\n        while(n>0){\r\n            a = a->next;\r\n            n--;\r\n        }\r\n        while(a->next!=NULL){\r\n            a = a->next;\r\n            b = b->next;\r\n        }\r\n        \r\n        b->next = b->next->next;\r\n        \r\n        return head;\r\n        \r\n    }\r\n};\r\n```\r\n\r\n#### result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/10898445/432ee692-817f-11e5-9205-c74181fac0de.png)\r\n\r\n#### Analysis\r\nthere is one cornor case, see the code below.\r\n\r\n### Attempt 3\r\n```c++\r\n/**\r\n * Definition for singly-linked list.\r\n * struct ListNode {\r\n *     int val;\r\n *     ListNode *next;\r\n *     ListNode(int x) : val(x), next(NULL) {}\r\n * };\r\n */\r\nclass Solution {\r\npublic:\r\n    ListNode* removeNthFromEnd(ListNode* head, int n) {\r\n        \r\n        if(head==NULL){\r\n            return NULL;\r\n        }\r\n       \r\n        \r\n        ListNode *a = head;\r\n        ListNode *b = head;\r\n        while(n>0){\r\n            a = a->next;\r\n            n--;\r\n        }\r\n        // a is null, means n is = length of the list, this is a cornor case\r\n        if(a==NULL){\r\n            return head->next;\r\n            \r\n        }\r\n        while(a->next!=NULL){\r\n            a = a->next;\r\n            b = b->next;\r\n        }\r\n        \r\n        b->next = b->next->next;\r\n        \r\n        return head;\r\n        \r\n    }\r\n};\r\n```\r\n\r\n#### result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/10898549/68c821ba-8180-11e5-99a7-032809f2ca99.png)"},"comment":{"url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/comments/194459771","html_url":"https://github.com/cbweixin/algorithm-practice/issues/53#issuecomment-194459771","issue_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/53","id":194459771,"user":{"login":"cbweixin","id":1326906,"avatar_url":"https://avatars.githubusercontent.com/u/1326906?v=3","gravatar_id":"","url":"https://api.github.com/users/cbweixin","html_url":"https://github.com/cbweixin","followers_url":"https://api.github.com/users/cbweixin/followers","following_url":"https://api.github.com/users/cbweixin/following{/other_user}","gists_url":"https://api.github.com/users/cbweixin/gists{/gist_id}","starred_url":"https://api.github.com/users/cbweixin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cbweixin/subscriptions","organizations_url":"https://api.github.com/users/cbweixin/orgs","repos_url":"https://api.github.com/users/cbweixin/repos","events_url":"https://api.github.com/users/cbweixin/events{/privacy}","received_events_url":"https://api.github.com/users/cbweixin/received_events","type":"User","site_admin":false},"created_at":"2016-03-09T19:14:45Z","updated_at":"2016-03-09T19:14:45Z","body":"Redo\r\n\r\n### Attempt 1\r\n```java\r\n/**\r\n * Definition for singly-linked list.\r\n * public class ListNode {\r\n *     int val;\r\n *     ListNode next;\r\n *     ListNode(int x) { val = x; }\r\n * }\r\n */\r\npublic class Solution {\r\n    public ListNode removeNthFromEnd(ListNode head, int n) {\r\n        if(head==null||head.next==null) return head;\r\n        \r\n        ListNode prev = new ListNode(-1);\r\n        prev.next = head;\r\n        ListNode start = new ListNode(-2);\r\n        start = head;\r\n        ListNode then = new ListNode(-3);\r\n        then = start;\r\n        \r\n        for(int i = 0; i < n;i++){\r\n            then = then.next;\r\n        }\r\n        \r\n        while(then.next!=null){\r\n            then = then.next;\r\n            start = start.next;\r\n            prev = prev.next;\r\n        }\r\n        \r\n        // if n is the length of list\r\n        if(start==head){\r\n            prev.next = head.next;\r\n            head.next = null;\r\n            return prev.next;\r\n        }\r\n        else{\r\n            prev.next = start.next;\r\n            start.next = null;\r\n        }\r\n        \r\n        return head;\r\n        \r\n    }\r\n}\r\n```\r\n\r\n#### Result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/13646890/6f9b229c-e5e6-11e5-9f31-ad4ba5a5f524.png)\r\n\r\n#### Analysis\r\nfor test case [1,2], 2 , the pain point is here :-1: \r\n```java\r\nfor(int i = 0; i < n;i++){\r\n            then = then.next;\r\n        }\r\n```\r\nassume you have test case which shows below:\r\n\r\n![image](https://cloud.githubusercontent.com/assets/1326906/13647045/303d47aa-e5e7-11e5-81e6-7d2165ab50da.png)\r\n\r\nwhen n = 1; pointer `then` should not move. otherwise, it would move one more step. \r\n\r\n### Attempt 2\r\n```java\r\npublic class Solution {\r\n    public ListNode removeNthFromEnd(ListNode head, int n) {\r\n        if(head==null) return head;\r\n        \r\n        ListNode prev = new ListNode(-1);\r\n        prev.next = head;\r\n        ListNode start = new ListNode(-2);\r\n        start = head;\r\n        ListNode then = new ListNode(-3);\r\n        then = start;\r\n        \r\n        for(int i = 1; i < n;i++){\r\n            then = then.next;\r\n        }\r\n        \r\n        while(then.next!=null){\r\n            then = then.next;\r\n            start = start.next;\r\n            prev = prev.next;\r\n        }\r\n        \r\n        // if n is the length of list\r\n        if(start==head){\r\n            prev.next = head.next;\r\n            head.next = null;\r\n            return prev.next;\r\n        }\r\n        else {\r\n            prev.next = start.next;\r\n            start.next = null;\r\n        }\r\n        \r\n        return head;\r\n        \r\n    }\r\n}\r\n```\r\n\r\n#### Result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/13647222/ff9759fa-e5e7-11e5-9b42-fdf2374fbd89.png)\r\n\r\n### Summary\r\n2 cornor case:\r\n- when n is 1\r\n- when n is the total length of list\r\n- how many steps you should move ahead before hand.\r\n"}}