Reverse a singly linked list.

代码

package list;public class ReverseLinkedList {        /**     * 描述 Reverse a singly linked list.     *      * 1. 调转指针解法(非递归)     * 用三个指针 prev,cur,next ，紧紧相邻，不断前进，每次将 cur.next 指向 prev ，将 prev指向cur, cur 指向 next 。     */    public ListNode Solution1(ListNode head){                if(head == null || head.next == null)            return head;                ListNode prev = null;        ListNode cur = head;        while(cur != null){            ListNode next = cur.next;            cur.next= prev;            prev = cur;            cur = next;                    }                return prev;    }/** * 描述 Reverse a singly linked list. *  * 2. recursive 递归解法 *  */public ListNode Solution2(ListNode head){        if(head == null || head.next == null)        return head;    ListNode cur = head;        ListNode ret = recurList(cur.next);        ListNode tmp = ret;    while (tmp.next != null)        tmp = tmp.next;    tmp.next = head;    head.next = null;        return ret;}private ListNode recurList(ListNode head) {        if (head == null || head.next == null)      return head;        ListNode tail = Solution2(head);    return tail;}

}

测试

package list;import org.junit.Assert;import org.junit.Before;import org.junit.Test;public class ReverseLinkedListTest {private ReverseLinkedList s;        @Before        public void setUp() {         s = new ReverseLinkedList();        }         @Test    public void testSolution1() {                 ListNode one = new ListNode(1);        ListNode two = new ListNode(2);        ListNode three = new ListNode(3);        ListNode four = new ListNode(4);        ListNode five = new ListNode(5);                one.next = two;        two.next = three;        three.next = four;        four.next = five;        ListNode result = s.Solution1(one);//        Assert.assertEquals(expect, result);                ListNode tmp = result ;        while (tmp!= null){            System.out.println(tmp.val);            tmp = tmp.next;        }    }        @Test    public void testSolution2() {                 ListNode one = new ListNode(1);        ListNode two = new ListNode(2);        ListNode three = new ListNode(3);        ListNode four = new ListNode(4);        ListNode five = new ListNode(5);                one.next = two;        two.next = three;        three.next = four;        four.next = five;        ListNode result = s.Solution2(one);//        Assert.assertEquals(expect, result);                ListNode tmp = result ;        while (tmp!= null){            System.out.println(tmp.val);            tmp = tmp.next;        }    }}

结果

5432154321