package com.knox.leetcode;

import com.knox.leetcode.LinkedList.ListNode;


/*
* 206. 反转链表 https://leetcode-cn.com/problems/reverse-linked-list/
*
* 反转一个单链表。
* 输入: 1->2->3->4->5->NULL
* 输出: 5->4->3->2->1->NULL
*
* */
public class _206_reverseList {

    private static class Solution {
        public ListNode reverseList(ListNode head) {
//            return reverseList_v1(head);
            return reverseList_v2(head);
        }

        // 递归结果
        private ListNode reverseList_v1(ListNode head) {
            if (head == null || head.next == null) return head;

            ListNode next = head.next;
            // 经过翻转, next结点已经是翻转后链表的尾结点了, 所以只需要把next.next指向head
            // 但此时, head.next还有值, 所以需要把它清空
            ListNode newHead = reverseList_v1(next);
            next.next = head;
            head.next = null;
            return newHead;
        }

        // 迭代解法
        private ListNode reverseList_v2(ListNode head) {
            if (head == null || head.next == null) return head;

            ListNode dummy = new ListNode();
            ListNode node = head.next;
            head.next = null; //第一个结点翻转后会变为最后一个结点, 需要把next清空。
            dummy.next = head;
            while (node != null) {
                ListNode next = node.next;
                // 当前结点放到新链表的第一个位置
                node.next = dummy.next;
                dummy.next = node;
                node = next;
            }

            return dummy.next;
        }
    }


    public static void main(String[] args) {
        Solution ins = new Solution();

        int[] arr1 = {1, 2, 3, 4, 5};
        ListNode head = LeetCodeHelper.createSingleLinkedListFromArray(arr1);
        ListNode ret = ins.reverseList(head);
        LeetCodeHelper.printLinkedList(ret);


    }
}

@@ -407,17 +407,17 @@
 seList_v
-2
+3
 (head);%0A
@@ -1450,16 +1450,731 @@
        %7D
+%0A%0A        /*%0A        * %E8%BF%AD%E4%BB%A3%E8%A7%A3%E6%B3%95%0A        * %E6%80%9D%E8%B7%AF%EF%BC%9A%0A        * 1. %E6%96%B0%E5%BB%BA%E4%B8%80%E4%B8%AA%E7%A9%BA%E9%93%BE%E8%A1%A8 newHead%0A        * 2. %E9%81%8D%E5%8E%86%E5%8E%9F%E9%93%BE%E8%A1%A8, %E6%8A%8A%E5%BD%93%E5%89%8D%E7%BB%93%E7%82%B9%E6%94%BE%E5%88%B0%E6%96%B0%E9%93%BE%E8%A1%A8%E7%AC%AC%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE%0A        * 3. %E6%94%BE%E5%88%B0%E6%96%B0%E9%93%BE%E8%A1%A8%E7%AC%AC%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE%E6%9C%89%E5%87%A0%E4%B8%AA%E5%85%B3%E9%94%AE%E4%B8%8D%E6%AD%A5%E9%AA%A4%0A        *   a) %E8%AE%B0%E5%BD%95%E5%8E%9F%E9%93%BE%E8%A1%A8%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9 next = head.next%0A        *   b) %E5%BD%93%E5%89%8D%E7%BB%93%E7%82%B9%E6%89%A7%E8%A1%8C%E6%96%B0%E9%93%BE%E8%A1%A8%E7%AC%AC%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9 head.next = newHead%0A        *   c) %E6%96%B0%E9%93%BE%E8%A1%A8%E5%A4%B4%E6%8C%87%E9%92%88%E6%8C%87%E5%90%91%E5%BD%93%E5%89%8D%E7%BB%93%E7%82%B9 newHead = head;%0A        *   d) %E7%BB%A7%E7%BB%AD%E8%BF%AD%E4%BB%A3, %E9%87%8D%E5%A4%8D%E4%B8%8A%E9%9D%A2%E6%AD%A5%E9%AA%A4%0A        *%0A        * */%0A        private ListNode reverseList_v3(ListNode head) %7B%0A            if (head == null %7C%7C head.next == null) return head;%0A%0A            ListNode newHead = null;%0A            while (head != null) %7B%0A                ListNode next = head.next;%0A                head.next = newHead;%0A                newHead = head;%0A                head = next;%0A            %7D%0A%0A            return newHead;%0A        %7D
 %0A    %7D%0A%0A
@@ -2413,32 +2413,32 @@
 erseList(head);%0A
+
         LeetCode
@@ -2466,18 +2466,16 @@
 t(ret);%0A
-%0A%0A
     %7D%0A%7D%0A

update 206_reverseList