本题来自左神《程序员面试代码指南》“反转单向和双向链表”题目。

题目

分别实现反转单向链表和反转双向链表的函数。

如果链表长度为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));}}