解法一:双指针迭代
使用两个指针(引用),分别标记当前遍历到的节点cur的前一个节点(pre),和后一个节点(next),具体的操作流程请看代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
因为反转链表的操作需要从头结点遍历至尾节点,所以,这个算法流程的时间复杂度为O(n)。
解法二:尾递归
代码如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
private ListNode reverse(ListNode pre,ListNode cur){
if(cur == null){
return pre;
}
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
return reverse(pre,next);
}
}
执行结果:
解法三:递归
代码如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode cur = reverseList(head.next);
// 1->2->3->4->5->null
// cur = 5 head = 4
head.next.next = head;
head.next = null;
return cur;
}
}
执行结果:
反转链表递归的思路比较难以理解,可以参考题解
需要说明的是:
head.next.next = head;
对于这一段代码,不能写成
cur.next = head;
因为cur是最后反转链表需要返回的值,也就是原链表的尾节点,为了保证递归的一致性,应该使用示例代码的写法。
对于递归和非递归的写法比较:时间复杂度上均为O(n),但是递归写法会隐式地调用栈空间,所以更推荐双指针迭代的写法。
网友评论