对经典Java面试问题1

**经典Java面试题：单链表反转**

###问题描述反转一个单链表的元素顺序。例如，原链表为 `1 ->2 ->3 ->4`, 反转后变为 `4 ->3 ->2 ->1`。

### 解决方案#### 方法一：递归法

java// Node类定义class Node {
 int data;
 Node next;

 public Node(int data) {
 this.data = data;
 this.next = null;
 }
}

public class LinkedListReverse {
 // 递归反转链表 public static Node reverse(Node head) {
 if (head == null || head.next == null) {
 return head; // 链表长度为1或0，直接返回 }

 Node newHead = reverse(head.next); // 递归反转后半段 head.next.next = head; // 反转指针 head.next = null; // 断开原链 return newHead;
 }

 public static void main(String[] args) {
 Node head = new Node(1);
 head.next = new Node(2);
 head.next.next = new Node(3);
 head.next.next.next = new Node(4);

 System.out.println("Original List:");
 printList(head); // 打印原链表 head = reverse(head); // 反转链表 System.out.println("
Reversed List:");
 printList(head); // 打印反转后的链表 }

 // 打印链表元素 public static void printList(Node head) {
 while (head != null) {
 System.out.print(head.data + " ");
 head = head.next;
 }
 System.out.println();
 }
}

java// Node类定义class Node {
 int data;
 Node next;

 public Node(int data) {
 this.data = data;
 this.next = null;
 }
}

public class LinkedListReverseIterative {
 // 迭代反转链表 public static Node reverse(Node head) {
 if (head == null || head.next == null) {
 return head; // 链表长度为1或0，直接返回 }

 Node prev = null;
 Node curr = head;

 while (curr != null) {
 Node nextTemp = curr.next; // 缓存下一个节点 curr.next = prev; // 反转指针 prev = curr; // 移动prev指针 curr = nextTemp; // 移动curr指针 }

 return prev;
 }

 public static void main(String[] args) {
 Node head = new Node(1);
 head.next = new Node(2);
 head.next.next = new Node(3);
 head.next.next.next = new Node(4);

 System.out.println("Original List:");
 printList(head); // 打印原链表 head = reverse(head); // 反转链表 System.out.println("
Reversed List:");
 printList(head); // 打印反转后的链表 }

 // 打印链表元素 public static void printList(Node head) {
 while (head != null) {
 System.out.print(head.data + " ");
 head = head.next;
 }
 System.out.println();
 }
}