Reversing the single-way linked list

Answer 1

以下是在Java中实现单向链表反转的两种常见方法：

**一、迭代法**

1. **思路**
- 需要三个指针，分别表示当前节点（`cur`）、当前节点的前驱节点（`pre`）和当前节点的后继节点（`next`）。
- 初始时，`pre`为`null`，`cur`指向链表的头节点。
- 在遍历链表的过程中，先保存`cur`的后继节点到`next`，然后将`cur`的`next`指针指向`pre`，接着更新`pre`为`cur`，`cur`为`next`，直到`cur`为`null`，此时`pre`就是反转后的链表头节点。

2. **示例代码**
```java
class Node {
public int value;
public Node next;
public Node(int i) {
value = i;
next = null;
}
// 向链表中添加新节点
public void add(Node head, Node add) {
if (head == null) {
return;
}
while (head.next!= null) {
head = head.next;
}
head.next = add;
}
// 由头节点出发顺序遍历整个链表
public static void print(Node head) {
if (head == null) {
System.out.println("链表为空");
}
while (head!= null) {
System.out.print((head.value + " => "));
head = head.next;
}
}
// 反转链表（迭代的方式顺序逐步处理）
public static Node reverse(Node head) {
if (head == null || head.next == null) {
return head;
}
Node cur = head;
Node pre = null;
Node next = null;
while (cur!= null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}

```

**二、递归法**

1. **思路**
- 对于递归反转链表，基本思想是将链表除了头节点之外的部分先递归反转，然后将头节点连接到反转后的链表后面。
- 递归的终止条件是当链表只有一个节点或者为空时，直接返回该节点。

2. **示例代码**
```java
class Node {
public int value;
public Node next;
public Node(int i) {
value = i;
next = null;
}
// 递归方法反转链表
public Node reverseRecurrence(Node head) {
if (head.next == null) {
return head;
}
Node last = reverseRecurrence(head.next);
head.next.next = head;
head.next = null;
return last;
}
}
```
点击前往免费阅读更多精彩小说