反转链表 -- java
题目描述
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
链表节点定义如下：
public class ListNode {
int value;
ListNode next = null;
public ListNode() {
}
public ListNode(int value) {
this.value = value;
}
@Override
public String toString() {
return "ListNode{" +
"value=" + value +
'}';
}
}
解题思路
- 定义指向反转链表的头指针和指向当前节点、它的前一个节点、它的后一个节点的指针
- 循环链表中的节点
- 每次循环中，让当前节点指向前一个节点prev，之后把当前节点保存在prev中，以供下个节点使用
代码
public class ReverseList {
public static ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode reversedHead = null;
ListNode node = head;
ListNode prev = null;
while (node != null) {
ListNode next = node.next;
// 找到尾结点
if (next == null) {
reversedHead = node;
}
node.next = prev;
prev = node;
node = next;
}
return reversedHead;
}
// 测试
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
print_listNode(node1); // 反转前
print_listNode(reverseList(node1)); // 反转后
}
// 打印listNode(用作测试)
public static void print_listNode(ListNode listNode) {
while (listNode != null) {
System.out.print(listNode.value+" ");
listNode = listNode.next;
}
System.out.println();
}
}
来自：
《剑指Offer》
Coding-Interviews/反转链表.md at master · todorex/Coding-Interviews