【牛客】反转链表与指定区间链表反转
浏览 143 | 评论 0 | 字数 949
TTQ
2022年04月24日
  • 原题链接:https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca
    原题链接:https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c

    描述

    给出一个链表,要求实现翻转整个链表或者指定区间nm中的元素进行翻转。

    思路

    整个链表翻转很简单,遍历所有节点,将当前节点的next指向上一个节点即可,注意最后返回的要是上一个节点(当前节点已为空)。
    翻转指定区间内元素的链表也可以通过一次遍历完成翻转:只需要记录需要翻转的区间头,对其中的每个节点都放到区间头上去即可。

    代码

    翻转链表

    function ReverseList(pHead) {
      let cur = pHead;
      let pre = undefined;
      while (cur) {
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
      }
      return pre;
    }

    翻转链表指定区间

    function reverseBetween(head, m, n) {
      let res = new ListNode(null);
      res.next = head;
      let pre = res;
      let cur = head;
      for (let i = 1; i < m; i++) {
        pre = cur;
        cur = cur.next;
      }
      for (let i = m; i < n; i++) {
        let next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
      }
      return res.next;
    }
    本文作者:TTQ
    本文链接:https://blog.ponder.fun/archives/149.html
    最后修改时间:2022-04-24 16:02:49
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论