本題來自左神《程序員面試代碼指南》“反轉單向和雙向鏈表”題目。

題目

分別實現反轉單向鏈表和反轉雙向鏈表的函數。

如果鏈表長度為N，時間復雜度要求為O(N)，額外空間復雜度要求為O(1)。

題解

本題比較簡單，讀者做到代碼一次完成，運行不出錯即可。

• 反轉單向鏈表的函數如下（該函數返回反轉之后鏈表新的頭節點）
• 反轉雙向鏈表的函數如下（函數返回反轉之后鏈表新的頭節點）

package chapter_2_listproblem;public class Problem_04_ReverseList {public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}public static Node reverseList(Node head) {Node pre = null; // pre 始終指向頭插法得到的新鏈表的表頭Node next = null; // head 始終指向越來越短的原鏈表的表頭while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;}public static class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data) {this.value = data;}}public static DoubleNode reverseList(DoubleNode head) {DoubleNode pre = null;DoubleNode next = null;while (head != null) {next = head.next;head.next = pre;head.last = next;pre = head;head = next;}return pre;}public static void printLinkedList(Node head) {System.out.print("Linked List: ");while (head != null) {System.out.print(head.value + " ");head = head.next;}System.out.println();}public static void printDoubleLinkedList(DoubleNode head) {System.out.print("Double Linked List: ");DoubleNode end = null;while (head != null) {System.out.print(head.value + " ");end = head;head = head.next;}System.out.print("| ");while (end != null) {System.out.print(end.value + " ");end = end.last;}System.out.println();}// for testpublic static void main(String[] args) {Node head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);printLinkedList(head1);head1 = reverseList(head1);printLinkedList(head1);DoubleNode head2 = new DoubleNode(1);head2.next = new DoubleNode(2);head2.next.last = head2;head2.next.next = new DoubleNode(3);head2.next.next.last = head2.next;head2.next.next.next = new DoubleNode(4);head2.next.next.next.last = head2.next.next;printDoubleLinkedList(head2);printDoubleLinkedList(reverseList(head2));}}

總結

以上是生活随笔為你收集整理的左神算法：反转单向和双向链表（Java版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。