[Leetcode] Reverse Linked List 鏈表反轉（遞歸與非遞歸）

RyanHoo 發布于2019-08-15 14:03 / 3379人閱讀

摘要：代碼描述調轉指針解法非遞歸用三個指針，緊緊相鄰，不斷前進，每次將指向，將指向指向。描述遞歸解法測試結果

Reverse a singly linked list.

代碼
ReverseLinkedList.java

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

}

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

}

結果

GPU云服務器云服務器 python反轉鏈表樹形遞歸遞歸編程遞歸打印

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68479.html

LeetCode 206：反轉鏈表 Reverse Linked List

摘要：反轉一個單鏈表。示例輸入輸出進階你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題解題思路每次遍歷到最后一位取節點這種方法就算了時間復雜度太高。從鏈表末尾向頭部逐個分離節點，并將節點添加到新鏈表的末尾。與迭代法原理相似。反轉一個單鏈表。 Reverse a singly linked list. 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2...

Gilbertat 2019-08-16 18:39 評論0 收藏0
LeetCode 206：反轉鏈表 Reverse Linked List

摘要：反轉一個單鏈表。示例輸入輸出進階你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題解題思路每次遍歷到最后一位取節點這種方法就算了時間復雜度太高。從鏈表末尾向頭部逐個分離節點，并將節點添加到新鏈表的末尾。與迭代法原理相似。反轉一個單鏈表。 Reverse a singly linked list. 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2...

heartFollower 2019-07-31 11:29 評論0 收藏0
LeetCode 之 JavaScript 解答第206題 —— 反轉鏈表（Reverse Link

摘要：算法思路兩種方法一般反轉遞歸法一般解決定義三個指針，分別為，存儲當前結點，指向反轉好的結點的頭結點，存儲下一結點信息。遞歸法重點分析先確定終止條件當下一結點為時，返回當前節點判斷當前的鏈表是否為遞歸找到尾結點，將其存儲為頭結點。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿題目：Reverse...

zhangfaliang 2019-08-23 17:12 評論0 收藏0
[Leetcode] Reverse Linked List 反轉鏈表

摘要：先跳過前個節點，然后初始化好這五個指針后，用中的方法反轉鏈表。完成了第個節點的反轉后，將子鏈反轉前的頭節點的設為子鏈反轉過程中的下一個節點，將子鏈反轉前頭節點前面一個節點的設為子鏈反轉過程中的當前節點。 Reverse Linked List I Reverse a singly linked list. click to show more hints. Hint: A linke...

Eminjannn 2019-08-14 12:28 評論0 收藏0
LeetCode：206. 反轉鏈表

摘要：示例輸入輸出進階你可以迭代或遞歸地反轉鏈表。可以設置一個指針，指向，保證后續的操作然后將，往前挪動，當然還有，直到為空，這時指向反轉后鏈表的頭結點。接下來考慮遞歸結束的條件非常顯然，子鏈表只有一個節點是遞歸結束，直接返回該節點。本文來自 SoulOH 的CSDN 博客，原文地址請點擊：https://blog.csdn.net/SoulOH/... 題目:反轉一個單鏈表。示例: ...

wenshi11019 2019-08-23 12:08 評論0 收藏0