LeetCode-CSharp/Solution/0206.Reverse-linked-list/0206-Reverse-linked-list.cs at main · FakeStandard/LeetCode-CSharp · 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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using Common;
using System;
using System.Collections.Generic;
using System.Text;

namespace Solution._0206.Reverse_linked_list
{
    public class _0206_Reverse_linked_list
    {
        /// <summary>
        /// Recursively Solution
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public ListNode ReverseList(ListNode head)
        {
            if (head == null || head.next == null)
                return head;

            ListNode node = ReverseList(head.next);
            head.next.next = head;
            head.next = null;

            return node;
        }

        /// <summary>
        /// Iteratively Solution
        /// faster than the previous solution.
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        //public ListNode ReverseList(ListNode head)
        //{
        //    if (head == null) return head;

        //    ListNode prev = null;

        //    // 1->2->3->4->5
        //    while (head != null)
        //    {
        //        ListNode next = head.next;
        //        head.next = prev;
        //        prev = head;
        //        head = next;

        //        /* first time
        //         * next = 2->3->4->5
        //         * head.next = null
        //         * prev = 1
        //         * head = 2->3->4->5
        //         */
        //        /* second time
        //         * next = 3->4->5
        //         * head.next = 1
        //         * prev = 2->1
        //         * head = 3->4->5
        //         */
        //        /* next time
        //         * next = 4->5
        //         * head.next = 2->1
        //         * prev = 3->2->1
        //         * head = 4->5
        //         */
        //        /* next time
        //         * next = 5
        //         * head.next = 3->2->1
        //         * prev = 4->3->2->1
        //         * head = 5
        //         */
        //        /* the last time
        //         * next = null
        //         * head.next = 4->3->2->1
        //         * prev = 5->4->3->2->1
        //         * head = null
        //         */
        //    }

        //    return prev;
        //}

        /// <summary>
        /// Stack Solution
        /// the fastest solution, although not very smart.
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        //public ListNode ReverseList(ListNode head)
        //{
        //    if (head == null) return head;

        //    ListNode res = new ListNode();
        //    ListNode cur = res;

        //    Stack<int> stack = new Stack<int>();

        //    while (head != null)
        //    {
        //        stack.Push(head.val);
        //        head = head.next;
        //    }

        //    while (stack.Count > 0)
        //    {
        //        ListNode node = new ListNode(stack.Pop());
        //        cur.next = node;
        //        cur = cur.next;
        //    }

        //    return res.next;
        //}
    }
}