[Leetcode] Reverse Linked List 链表反转（递归与非递归）

RyanHoo 发布于2019-08-15 14:03 / 3273人阅读

摘要：代码描述调转指针解法非递归用三个指针，紧紧相邻，不断前进，每次将指向，将指向指向。描述递归解法测试结果

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

}

结果

海外云主机私有云 python反转链表树形递归递归编程递归打印

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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