反轉連結清單
牛客題霸NC78
難度：Easy
題目描述：
輸入一個連結清單，反轉連結清單後，輸出新連結清單的表頭。
示例：
輸入：
{1, 2, 3}
輸出：
{3, 2, 1}
解決方法：
1.通過棧+尾插法實作
可以将所有節點入棧，然後逐個出棧，插入到連結清單尾部。
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
Stack<ListNode> stack = new Stack<>();
while(head != null){
stack.push(head);
head = head.next;
}
ListNode newHead = null;
ListNode tail = null;
while(!stack.isEmpty()){
ListNode node = stack.pop();
node.next = null;
if(newHead == null){
newHead = node;
tail = node;
}
else{
tail.next = node;
tail = node;
}
}
return newHead;
}
}
2.頭插法
我們要将連結清單逆序，可以周遊原連結清單，對每個節點采用頭插法插入到新連結清單中即可實作反轉。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode newHead = null;
while(head != null){
ListNode nextNode = head.next;
head.next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}
}
3.通過遞歸實作
遞歸也可以實作連結清單反轉，但是效率比較低。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
// 一個或者沒有節點直接傳回
if(head == null || head.next == null){
return head;
}
// 反轉head.next為開始的連結清單
ListNode newHead = ReverseList(head.next);
// 将head節點放到連結清單尾部
head.next.next = head;
head.next = null;
return newHead;
}
}