精华内容
下载资源
问答
  • 反转链表

    2020-05-16 15:36:14
    反转链表反转链表相关算法206. 反转链表 反转链表相关算法 在这里记录反转链表相关问题 206. 反转链表 206. 反转链表 解法1:【迭代法】在遍历列表时,将当前节点的 next 指针改为指向前一个元素。由于节点没有引用...

    反转链表相关算法

    在这里记录反转链表相关问题

    206. 反转链表

    206. 反转链表

    解法1:【迭代法】在遍历列表时,将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储下一个节点。记在最后返回新的头引用。

    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var reverseList = function(head) {
        let pre = null
        let cur = head
        while(cur){
            let temNext = cur.next
            cur.next = pre
            pre = cur
            cur = temNext
        }
        return pre
    };
    

    解法2:【递归法】

    var reverseList = function(head) {
        if(!head || !head.next)return head
        let p = reverseList(head.next)
        head.next.next = head
        head.next = null
        return p
    };
    

    92. 反转链表 II

    92. 反转链表 II

    解题思路

    参考了一位大佬的思路:
    找到要反转的位置,进行n-m次反转,这里的反转操作为:每一次将后一位放到要反转的表头。
    例如 1->2->3->4->5,m = 2, n = 4
    反转部分:2->3->4 此时head 2 nxt 3
    需要反转m-n = 2次:
    第一次反转: 3->2->4 此时head 2 nxt 4
    第二次反转:4->3->2

    需要注意的是要记住反转部分的前一个节点,完成衔接。

    代码

    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode} head
     * @param {number} m
     * @param {number} n
     * @return {ListNode}
     */
    var reverseBetween = function(head, m, n) {
        // 用来记住整个链表的头节点位置
        let res = new ListNode(0)
        res.next = head
        // 找到需要反转的位置
        let pre = res
        for(let i = 1; i < m; ++i){
            pre = pre.next
        }
        // 将head指向要反转的链表部分的头部
        head = pre.next
        for(let i = m; i < n; ++i){
            let nxt = head.next
            // nxt 节点要被放到反转部分的头部,所以将head的next指向它的下下个节点
            head.next = head.next.next
            // 将nxt放到头部,pre.next指向的是反转部分的头部节点
            nxt.next = pre.next
            // 重新将pre指向反转部分的头部
            pre.next = nxt
        }
        return res.next
    };
    

    参考链接:https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode/

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 63,297
精华内容 25,318
关键字:

反转链表