資訊專欄INFORMATION COLUMN
摘要：代碼描述調(diào)轉(zhuǎn)指針解法非遞歸用三個指針，緊緊相鄰，不斷前進(jìn)，每次將指向，將指向指向。描述遞歸解法測試結(jié)果
Reverse a singly linked list.
代碼
ReverseLinkedList.java
package list;
public class ReverseLinkedList {
/**
* 描述 Reverse a singly linked list.
*
* 1. 調(diào)轉(zhuǎn)指針解法(非遞歸)
* 用三個指針 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;
}
}
測試
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é)果
5 4 3 2 1 5 4 3 2 1
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68479.html
摘要：反轉(zhuǎn)一個單鏈表。示例輸入輸出進(jìn)階你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題解題思路每次遍歷到最后一位取節(jié)點這種方法就算了時間復(fù)雜度太高。從鏈表末尾向頭部逐個分離節(jié)點，并將節(jié)點添加到新鏈表的末尾。與迭代法原理相似。 反轉(zhuǎn)一個單鏈表。 Reverse a singly linked list. 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2...
摘要：反轉(zhuǎn)一個單鏈表。示例輸入輸出進(jìn)階你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題解題思路每次遍歷到最后一位取節(jié)點這種方法就算了時間復(fù)雜度太高。從鏈表末尾向頭部逐個分離節(jié)點，并將節(jié)點添加到新鏈表的末尾。與迭代法原理相似。 反轉(zhuǎn)一個單鏈表。 Reverse a singly linked list. 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2...
摘要：算法思路兩種方法一般反轉(zhuǎn)遞歸法一般解決定義三個指針，分別為，存儲當(dāng)前結(jié)點，指向反轉(zhuǎn)好的結(jié)點的頭結(jié)點，存儲下一結(jié)點信息。遞歸法重點分析先確定終止條件當(dāng)下一結(jié)點為時，返回當(dāng)前節(jié)點判斷當(dāng)前的鏈表是否為遞歸找到尾結(jié)點，將其存儲為頭結(jié)點。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿 題目：Reverse...
摘要：先跳過前個節(jié)點，然后初始化好這五個指針后，用中的方法反轉(zhuǎn)鏈表。完成了第個節(jié)點的反轉(zhuǎn)后，將子鏈反轉(zhuǎn)前的頭節(jié)點的設(shè)為子鏈反轉(zhuǎn)過程中的下一個節(jié)點，將子鏈反轉(zhuǎn)前頭節(jié)點前面一個節(jié)點的設(shè)為子鏈反轉(zhuǎn)過程中的當(dāng)前節(jié)點。 Reverse Linked List I Reverse a singly linked list. click to show more hints. Hint: A linke...
摘要：示例輸入輸出進(jìn)階你可以迭代或遞歸地反轉(zhuǎn)鏈表?？梢栽O(shè)置一個指針，指向，保證后續(xù)的操作然后將，往前挪動，當(dāng)然還有，直到為空，這時指向反轉(zhuǎn)后鏈表的頭結(jié)點。接下來考慮遞歸結(jié)束的條件非常顯然，子鏈表只有一個節(jié)點是遞歸結(jié)束，直接返回該節(jié)點。 本文來自 SoulOH 的CSDN 博客 ，原文地址請點擊：https://blog.csdn.net/SoulOH/... 題目:反轉(zhuǎn)一個單鏈表。 示例: ...
閱讀 2091·2021-11-23 10:13
閱讀 2799·2021-11-09 09:47
閱讀 2743·2021-09-22 15:08
閱讀 3323·2021-09-03 10:46
閱讀 2239·2019-08-30 15:54
閱讀 921·2019-08-28 18:09
閱讀 2433·2019-08-26 18:26
閱讀 2346·2019-08-26 13:48
