Tags

,

Reverse a singly linked list.

Solution : use fake head will be easy.

        public ListNode ReverseList(ListNode head)
        {
            var fakeHead = new ListNode(-1);

            while (head != null)
            {
                var next = head.next;

                head.next = fakeHead.next;
                fakeHead.next = head;

                head = next;
            }

            return fakeHead.next;
        }

Solution 2: Share this cool recursive solution.

    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        var rest = ReverseList(head.next);

        head.next.next = head;
        head.next = null;

        return rest;    
    }

follow up question:

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Solution : 1. create a fake head; 2. move m – 1 step to the node need to reverse. 3. reverse until n

            var fakehead = new ListNode(-1){next = head};

            var start = Utility.Move(fakehead, m - 1);

            var count = m;
            var mNode = start.next;
            while (count < n)
            {
                // reverse linked list
                var firstNode = start.next;
                start.next = mNode.next;
                mNode.next = mNode.next.next;
                start.next.next = firstNode;

                count++;
            }

            return fakehead.next;