[Algorithm] 206. Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLFollow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Approach #1 (Iterative) [Accepted]
Assume that we have linked list 1 → 2 → 3 → Ø
, we would like to change it to Ø ← 1 ← 2 ← 3
.
While you are traversing the list, change the current node's next pointer to point to its previous element. Since a node does not have reference to its previous node, you must store its previous element beforehand. You also need another pointer to store the next node before changing the reference. Do not forget to return the new head reference at the end!
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
Complexity analysis
-
Time complexity : O(n)O(n). Assume that nn is the list's length, the time complexity is O(n)O(n).
-
Space complexity : O(1)O(1).
Approach #2 (Recursive) [Accepted]
The recursive version is slightly trickier and the key is to work backwards. Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let's assume the list is: n1 → … → nk-1 → nk → nk+1 → … → nm → Ø
Assume from node nk+1 to nm had been reversed and you are at node nk.
n1 → … → nk-1 → nk → nk+1 ← … ← nm
We want nk+1’s next node to point to nk.
So,
nk.next.next = nk;
Be very careful that n1's next must point to Ø. If you forget about this, your linked list has a cycle in it. This bug could be caught if you test your code with a linked list of size 2.
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
Complexity analysis
-
Time complexity : O(n)O(n). Assume that nn is the list's length, the time complexity is O(n)O(n).
-
Space complexity : O(n)O(n). The extra space comes from implicit stack space due to recursion. The recursion could go up to nn levels deep.
相关文章
- Java8 基本类型数组转换为List[通俗易懂]
- java list 转json 字符串_JSON的String字符串与Java的List列表对象的相互转换
- java list 转json 字符串_Java之JSON字符串与List集合之间相互转换
- mybatis 查询返回List集合、map集合、List<Map>集合[通俗易懂]
- 小程序正式版报错600002 url not in domain list
- Java基础——List、Set、Map的简单操作与遍历
- ORA-25248: duplicate agent specified in the agent list ORACLE 报错 故障修复 远程处理
- ORA-13053: maximum number of geometric elements in argument list exceeded ORACLE 报错 故障修复 远程处理
- ORA-14177: STORE-IN (Tablespace list) can only be specified for a LOCAL index on a Hash or Composite Range Hash table ORACLE 报错 故障修复 远程处理
- 《Drools7.0.0.Final规则引擎教程》相同对象and List使用详解编程语言
- MySQL Status Mysqlx_stmt_list_notices 数据库状态作用意思及如何正确
- Java List.contains()方法:判断列表中是否包含指定元素
- Hibernate Query接口 list方法:返回查询结果的List集合
- 类型探索Redis中List数据结构的优势(redis中的list)
- Mysql实现List存储的技巧(mysql存储list)
- 监测redis List动态稳定性突破极限(监听redis list)
- 简单快速修改Redis List技巧(修改redis的list)
- 使用Redis实现List存储(向redis中存list)