143. Reorder List

Problem Statement

link: https://leetcode.com/problems/reorder-list/ https://leetcode.cn/problems/reorder-list/

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example:

Input: root = [1,2,3] Output: 25

Input: root = [4,9,0,5,1] Output: 1026

Solution Approach

To reorder the list as specified, first find the middle of the linked list, reverse the second half, and then merge the two halves together.

Algorithm

1. Finding the Middle of the List: Use the slow and fast pointers approach. Move one pointer one step at a time and the other two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.
2. Reverse the Second Half: Starting from the middle (found using the slow pointer), reverse the second half of the linked list.
3. Merge the Two Halves: Start from the head and the beginning of the reversed half, and alternately merge nodes from the first half and the reversed half to achieve the desired reorder.

Implement

    class Solution:
      def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
          n = len(gas)
          total = cur = 0
          start = 0
          for i in range(n):
              remainder = gas[i] - cost[i]
              total += remainder
              cur += remainder
              if cur < 0:
                  cur = 0
                  start = i + 1
          return start if total >=0 else -1

    
    

Twitter  facebook  Email