算法通关村第二关—手写链表反转(青铜)

       链表反转的三种方式 一、建立虚拟头结点辅助反转

 为了方便反转，可以创建一个ans结点，让ans.next = head,然后后面的结点一次插入到ans.next
 在下图中，对（1->2->3->4->5）进行反转，可以创建ans，让ans.next = node(1),然后依次把2，3，4，5结点插入到ans后面

//方法1：虚拟结点法 public static ListNode reverseList(ListNode head){ ListNode ans new ListNode(-1); ListNode cur head; while（cur != null){ ListNode next = cur.next; cur.next = ans.next; ans.next = cur; cur = next; } return ans.next; }

二、直接操作链表实现反转

 有时候面试官会让你使用难度更高一些的，不借助虚拟结点的方式来反转链表
 观察反转前后的指针指向，思考如何进行反转

 在初始状态中，cur指向的是旧链表的头结点，prev指向新链表的头结点，next指向下一个要调整的结点。在变化过程中，cur结点会转移到新结点中，然后prev指到cur到结点，cur指到next的结点。
核心代码如下：
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;

public ListNode reverseList(ListNode head){ ListNode prev = null; ListNode curr = head; while(curr != null){ ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; )

三、拓展（递归）

 还不太懂递归的写法，等以后学得深了再看看。

public ListNode reverseList(ListNode head){ if (head = null || head.next = null) return head; ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }