輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭，
思路一：
新建一個頭結點，遍歷原鏈表，每遍歷一個節點，就將新的節點插入到頭結點的后面
注意鏈表的保存
public static ListNode ReverseList(ListNode head) {
if(head == null||head.next == null)return head;//如果只有一個節點，不需要轉換
ListNode tempHead = new ListNode(0);//輔助頭結點
ListNode cur = head;//原鏈表輔助指標
ListNode next = null;//保存后面的鏈表
while (true){
if(cur == null)break;
next = cur.next;//保存后面的鏈表
cur.next = tempHead.next;
tempHead.next = cur;
//原鏈表向后挪動
cur = next;
}
return tempHead.next;
}
思路二：
- 使用堆疊，遍歷第一遍，將所有節點依次放入堆疊中
- 依次彈堆疊，組成新的鏈表即可
/**
* 使用堆疊實作單鏈表的反轉
* 1、將鏈表放入堆疊中
* 2、一次從堆疊中取出夠成一個新的鏈表即可
*/
public void reverseLinkedByStack() {
if (HeadNode.next == null) {
System.out.println("當前鏈表為空");
return;
}
Node temp = HeadNode.next;
Stack<Node> stack = new Stack<>();
//遍歷鏈表，放入堆疊中
while (true) {
stack.push(temp);
if (temp.next == null) break;
temp = temp.next;
}
//遍歷完成后，逐個彈堆疊，重新構成新的鏈表即可
temp = HeadNode;
while (!stack.empty()) {
temp.next = stack.pop();
temp = temp.next;
}
temp.next = null;//最后一個元素next域置為空
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/250261.html
標籤：其他