[Leetcode] Reverse Linked List 鏈表反轉(zhuǎn)（遞歸與非遞歸）

RyanHoo 發(fā)布于2019-08-15 14:03 / 3374人閱讀

摘要：代碼描述調(diào)轉(zhuǎn)指針解法非遞歸用三個(gè)指針，緊緊相鄰，不斷前進(jìn)，每次將指向，將指向指向。描述遞歸解法測(cè)試結(jié)果

Reverse a singly linked list.

代碼
ReverseLinkedList.java

package list;

public class ReverseLinkedList {
    
    /**
     * 描述 Reverse a singly linked list.
     * 
     * 1. 調(diào)轉(zhuǎn)指針解法(非遞歸)
     * 用三個(gè)指針 prev,cur,next ，緊緊相鄰，不斷前進(jìn)，每次將 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;
}

}

測(cè)試
ReverseLinkedListTest

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;
        }
    }

}

結(jié)果