这道题弄的心好累。。

 【】206

描述：

Reverse a singly linked list.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

 

思路：

增加一个全局节点newHead，用来指向新的头部，用用一个临时节点next来遍历整个链表，用来当旧的头部head，例如链表1-2-3-4，第一遍循环，newhead指向1，指向null，head是2,指向剩余的链表，2-3-4，然后第二遍循环，newhead指向2-1，head指向剩余的链表，3-4。。。以此类推，直到循环结束。

 

// iterative solutionpublic ListNode reverseList(ListNode head) {    ListNode newHead = null;    while(head != null){        ListNode next = head.next;        head.next = newHead;        newHead = head;        head = next;    }    return newHead;}

 

还有递归的算法：

 

// recursive solutionpublic ListNode reverseList(ListNode head) {    return reverseListInt(head, null);}public ListNode reverseListInt(ListNode head, ListNode newHead) {    if(head == null)        return newHead;    ListNode next = head.next;    head.next = newHead;    return reverseListInt(next, head);}