美文网首页
leetcode206.反转链表

leetcode206.反转链表

作者: 憨憨二师兄 | 来源:发表于2020-04-13 11:49 被阅读0次

    题目链接

    解法一:双指针迭代

    使用两个指针(引用),分别标记当前遍历到的节点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),但是递归写法会隐式地调用栈空间,所以更推荐双指针迭代的写法。

    相关文章

      网友评论

          本文标题:leetcode206.反转链表

          本文链接:https://www.haomeiwen.com/subject/anlumhtx.html