标签：head slow ListNode 题解 fast next 链表 result LeetCode

LeetCode 链表的中间结点算法题解 All In One

js / ts 实现重排链表

链表的中间结点原理 图解

// 快慢指针

function middleNode(head: ListNode | null): ListNode | null {
  // 快慢指针
  let slow = head;
  let fast = head?.next;
  while(fast && fast.next && fast.next.next) {
    // fast  每次前进两步
    fast = fast.next.next;
    // slow 每次前进一步
    slow = (slow as ListNode).next;
    // slow = slow.next;
    // Object is possibly 'null'.ts(2531)
  }
  return slow?.next || slow;
  // return slow?.next ? slow.next : slow;
};

876. 链表的中间结点

"use strict";

/**
 *
 * @author xgqfrms
 * @license MIT
 * @copyright xgqfrms
 * @created 2022-08-26
 * @modified
 *
 * @description 876. 链表的中间结点
 * @description 876. Middle of the Linked List
 * @difficulty Easy
 * @ime_complexity O(n)
 * @space_complexity O(n)
 * @augments
 * @example
 * @link https://leetcode.com/problems/middle-of-the-linked-list/
 * @link https://leetcode.cn/problems/middle-of-the-linked-list/
 * @solutions
 *
 * @best_solutions
 *
 */

export {};

const log = console.log;


// singly-linked list
class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
  }
  // add
  // remove
}


function middleNode(head: ListNode | null): ListNode | null {
  // 快慢指针
  let slow = head;
  let fast = head?.next;
  while(fast && fast.next && fast.next.next) {
    // fast  每次前进两步
    fast = fast.next.next;
    // slow 每次前进一步
    slow = (slow as ListNode).next;
    // slow = slow.next;
    // Object is possibly 'null'.ts(2531)
  }
  return slow?.next || slow;
  // return slow?.next ? slow.next : slow;
};

/*

测试用例

[1,2,3,4,5]
[1,2,3,4,5,6]
[1]

 */

// 测试用例 test cases
const testCases = [
  {
    input: [1,2,3,4,5],
    result:[3,4,5],
    desc: 'value equal to [3,4,5]',
  },
  {
    input: [1,2,3,4,5,6],
    result: [4,5,6],
    desc: 'value equal to [4,5,6]',
  },
  {
    input: [1],
    result: [1],
    desc: 'value equal to [1]',
  },
];


function LinkedListGenerator(arr: number[]) {
  let head;
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    if(i === 0) {
      head = new ListNode(arr[len - 1 - i], null);
    } else {
    let temp = new ListNode(arr[len - 1 - i], null);
      temp.next = head ;
      head = temp;
    }
  }
  // console.log(head);
  return head;
}

for (const [i, testCase] of testCases.entries()) {
  const head = LinkedListGenerator(testCase.input);
  const result = middleNode(head);
  const resultHead = LinkedListGenerator(testCase.result);
  log(`test case i result: \n`, JSON.stringify(result) === JSON.stringify(resultHead) ? `passed ✅` : `failed ❌`, result);
  // log(`test case i result: \n`, result.join('') === testCase.result.join('') ? `passed ✅` : `failed ❌`, result);
  // log(`test case i =`, testCase);
}


/*

$ npx ts-node ./876\ middle-of-the-linked-list.ts

*/

https://leetcode.com/problems/middle-of-the-linked-list/
https://leetcode.cn/problems/middle-of-the-linked-list/

LeetCode 题解 / LeetCode Solutions

https://www.youtube.com/results?search_query=+Leetcode+876

<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/wmpivqMlClI?start=4" title="YouTube video player" width="560"></iframe>

https://www.youtube.com/playlist?list=PLamwFu9yMruCBtS2tHUD77oI_Wsce-syE

https://www.youtube.com/channel/UCftIXZeipv4MTVwmfFphtYw/videos

<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/u0vcs_jZ1A8?start=26" title="YouTube video player" width="560"></iframe>

https://neetcode.io/

<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/WwfhLC16bis?start=37" title="YouTube video player" width="560"></iframe>

类似问题

LeetCode 206. Reverse Linked List / 反转链表

https://leetcode.com/problems/reverse-linked-list/

<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/G0_I-ZF0S38?start=5" title="YouTube video player" width="560"></iframe>

LeetCode 92. Reverse Linked List II / 反转链表 2

https://leetcode.com/problems/reverse-linked-list-ii/

<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/RF_M9tX4Eag?start=37" title="YouTube video player" width="560"></iframe>

refs

---

---

©xgqfrms 2012-2020

www.cnblogs.com/xgqfrms 发布文章使用：只允许注册用户才可以访问！

原创文章，版权所有©️xgqfrms, 禁止转载

标签：head,slow,ListNode,题解,fast,next,链表,result,LeetCode
From： https://www.cnblogs.com/xgqfrms/p/16628518.html