剑指 Offer 24. 反转链表(leetcode每日打卡)
题目描述
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路
双指针法
在遍历链表时,将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。
题解
class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head, pre = null; while(cur != null) { ListNode tmp = cur.next; // 暂存后继节点 cur.next//直接指向空链表就断掉了 cur.next = pre; // 修改 next 引用指向 pre = cur; // pre 暂存 cur cur = tmp; // cur 访问下一节点 } return pre; } }
复杂度
时间复杂度 O(N) : 遍历链表使用线性大小时间。 空间复杂度 O(1) : 变量 pre 和 cur 使用常数大小额外空间。
。