LeetCode/19.cpp at master · nitin-maharana/LeetCode · GitHub

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
/*
 * Written by Nitin Kumar Maharana
 * nitin.maharana@gmail.com
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    int len;

    void findLength(ListNode* head)
    {
        len = 0;

        while(head)
        {
            len++;
            head = head->next;
        }
    }

    int removeNodeFromEnd1(ListNode* head, int n)
    {
        if(!head)
            return 0;

        int num;

        num = removeNodeFromEnd1(head->next, n);

        if(num == n)
            head->next = head->next->next;

        return num+1;
    }

    void removeNodeFromEnd2(ListNode* head, int n)
    {
        ListNode *ptr1, *ptr2;

        ptr1 = head;

        for(int i = 0; i < n; i++)
            ptr1 = ptr1->next;

        ptr2 = head;

        while(ptr1->next)
        {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }

        ptr2->next = ptr2->next->next;
    }
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head)
            return NULL;

        findLength(head);

        if(len == n)
            return head->next;

        len = len - n - 1;
        ListNode *ptr = head;

        while(len--)
            ptr = ptr->next;

        ptr->next = ptr->next->next;

        return head;
    }

    ListNode* removeNthFromEnd1(ListNode* head, int n) {
        ListNode newHead(1);
        newHead.next = head;
        head = &newHead;

        if(random() % 2)
            removeNodeFromEnd1(head, n);
        else
            removeNodeFromEnd2(head, n);

        return head->next;
    }
};