返回
反转链表:Java巧夺天工
Android
2023-09-09 16:37:30
算法概述
反转链表算法的基本思想是,使用两个指针来遍历链表。第一个指针指向当前节点,第二个指针指向当前节点的前一个节点。在遍历过程中,将当前节点的下一个指针指向第二个指针,并将第二个指针指向当前节点。如此循环下去,直到遍历完整个链表,即可得到反转后的链表。
算法步骤
- 初始化两个指针:当前节点指针curr和前一个节点指针prev,两者均指向链表的头结点。
- 将curr的下一个指针指向prev。
- 将prev指向curr。
- 将curr指向curr的下一个节点。
- 重复步骤2、3、4,直到curr为null。
- 返回prev指向的节点,即反转后的链表的头结点。
代码实现
public class ReverseLinkedList {
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
ListNode reversedHead = reverseList(head);
while (reversedHead != null) {
System.out.print(reversedHead.val + " ");
reversedHead = reversedHead.next;
}
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
算法分析
- 时间复杂度:O(n)。算法需要遍历整个链表一次,因此时间复杂度为O(n)。
- 空间复杂度:O(1)。算法不需要额外的空间,因此空间复杂度为O(1)。
总结
反转链表算法是一种经典算法问题,其目的是将链表中节点的顺序颠倒。本文介绍了一种使用Java实现的反转链表算法,该算法具有O(1)的空间复杂度和O(n)的时间复杂度。