206--Reverse A Singly Linked List

package LinedList;

public class ReverseASinglyLinkedList {
    //解法一：迭代。
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return current;
    }
        /**
         * 解法二：递归
         * 递归的思路其实和迭代一样，就是处理两个节点，让它们之间的指针反转。
         * 只是，迭代是从头到尾依次处理，需要一个额外的指针来指向下一个节点。
         * 而递归是从尾到头，回溯的时候会有当前的节点，所以不需要额外的指针。
         * 还需要注意的是：p是反转后的整个链表的头节点，它第一次找到后，就没有作任何处理。
         *      而不是每次要处理（反转）的那个节点。
         */
    public ListNode reverseList2(ListNode head) {
        if (head==null||head.next==null)
            return head;
        ListNode p=reverseList2(head.next);
        head.next.next=head;
        head.next=null;
        return p;
    }
}
巴特西

206--Reverse A Singly Linked List

最新文章

热门文章
