[LeetCode] 876. Middle of the Linked List

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

The fast and slow pointer approach :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null  && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return slow;
    }
}

[LeetCode] 369. Plus One Linked List

 Problem : https://leetcode.com/problems/plus-one-linked-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        // reverse list
        ListNode reversed = reverse(head);
        
        int carry = 1;    
        ListNode p = reversed;
        ListNode last = null;
        
        while(p != null) {
            int total = p.val + carry;
            p.val = total % 10;
            carry = total / 10;
            last = p;
            p = p.next;
        }
        
        if (carry != 0) {
            last.next = new ListNode(carry);
        }
        
        
        return reverse(reversed);
    }
    
    ListNode reverse(ListNode head) {
        ListNode last = null;
        ListNode current = head;
        ListNode next = head.next;
        
        while (next != null) {
            current.next = last;
            last = current;
            current = next;
            next = current.next;
        }
        
        // remember to link the last element!
        current.next = last;
        return current;
    }
}

[LeetCode] 1019. Next Greater Node in Linked List

 Problem : https://leetcode.com/problems/next-greater-node-in-linked-list/

Use postorder traversal and maintain a decreasing monotonic stack.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        
        def postorder(node):
            if node.next:
                stack = postorder(node.next)
                while stack and stack[-1] <= node.val:
                    stack.pop()
                
                result.append(stack[-1] if stack else 0)                
                stack.append(node.val)
                
                return stack
            else:
                result.append(0)
                return [node.val]
        
        postorder(head)
        return result[::-1]

Or maintain a increasing monotonic stack which also saves the position of each smaller value.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        stack = []
        
        while head:
            while stack and stack[-1][1] < head.val:
                result[stack[-1][0]] = head.val
                stack.pop()
            
            stack.append([len(result), head.val])
            result.append(0)
            
            head = head.next
        
        return result

[LeetCode] 382. Linked List Random Node

 Problem : https://leetcode.com/problems/linked-list-random-node/

The naive way is calculating the length of the list first, then randomize the position in the list. But how to get the random node when it is expensive to get the list length. For example, assume the list is saved on remote server and the operation 'getNext' is very expensive. How to collect get the random node with minimal cost?

The answer is Reservoir sampling.

To make the problem more generically, let's say we need to sample k elements.

Suppose we have an element at the position of i ( i > k ), when we reach the element, the chance to select this element is  k / i.

Later on, we can select another element to replace the ith element.  For i+1 element, the change for it is not be selected is  1 - 1 / (i+1) = i / (i+1). 

So if ith element will eventually be selected, its chance is:

(the probability of ith element be selected ) * (  the probability of i+1th element not be selected to replace ith element) 

= (k / i ) *  (1 - 1 / (i+1)) 

= (k/i) * (i / i+1) 

= k / (i+1).    

def reservoirSample(S, R, K):
    """
    S : the items to sample
    R : the selected sample items
    K : number of the needed sample items
    """
	
    # fill the reservoir array
    for i in range(K):
        R[i] = S[i]
        
    # replace elements with gradually decreasing probability
    for i in range(K, len(S)):
        j = random.randint(0, i)
        if j <= k:
            R[j] = S[i]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode head;
    Random random = new Random();
    
    public Solution(ListNode head) {
        this.head = head;    
    }
    
    public int getRandom() {
        
        ListNode p = this.head;
        
        int result = p.val;
        int count = 1;
        p = p.next;
        
        while (p != null) {
            count += 1;
            
            if (random.nextInt(count) == 0) {
                result = p.val;
            }
            p = p.next;
        }
        
        return result;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

Edited on 1/7/2022. Replaced with reservoir sample solution.

[LeetCode] 381. Insert Delete GetRandom O(1) - Duplicates allowed

 Problem: https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

Similar to the problem # 380, to get O(1) time complexity for deleting operation, we need to save the index of each value in the value list.  Because it allows duplicated value be inserted and deleting item from bidirectional linked list is O(1). we can manage nodes with same value in a bidirectional linked list. Then the hash table saves the index of the last item of one value's bidirectional linked list. 

class Node:
    def __init__(self, val, pre, nxt):
        self.val = val
        self.pre = pre
        self.nxt = nxt
        
        
class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        # nodes with same value are linked as a bidirectional linked list
        # dict[K] save the index of the last node of number K's linked list 
        self.dict = defaultdict(lambda: -1)
        
        # save all values
        self.list = []
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        
        index = len(self.list)
        
        if self.dict[val] == -1:
            node = Node(val = val, pre = -1, nxt = -1)
            
            self.dict[val] = index
            self.list.append(node)
            
            return True
        else:
            pre = self.dict[val]
            node = Node(val = val, pre = pre, nxt = -1)
            
            # append to the existing bidirectional link
            
            preNode = self.list[pre]
            preNode.nxt = index
            
            self.dict[val] = index
            self.list.append(node)
            
            return False

    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        
        if self.dict[val] == -1:
            return False
        
        # use the last item of self.list to replace the removed item
        # and update the the altered item indices
        
        index = self.dict[val]
        node = self.list[index]
        
        if node.pre == -1:
            self.dict[val] = -1
        else:
            # remove from the removed node's bidirectional linked list
            self.dict[val] = node.pre
            self.list[node.pre].nxt = -1
            
        tailIndex = len(self.list) - 1
        tailNode = self.list.pop()

        if index != tailIndex:
            self.list[index] = tailNode

            # update tailNode's bidirectional linked list
            if self.dict[tailNode.val] == tailIndex:
                self.dict[tailNode.val] = index

            if tailNode.pre != -1:
                self.list[tailNode.pre].nxt = index

            if tailNode.nxt != -1:
                self.list[tailNode.nxt].pre = index
                
        return True
    
    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        
        index = random.randint(0, len(self.list) - 1)
        return self.list[index].val


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

P.S. We can also use hash set to save all list item indices of a given value. Deleting item from hash set is also O(1).

[LeetCode] 328. Odd Even Linked List

 Problem : https://leetcode.com/problems/odd-even-linked-list/

Use dummy list to save odd and even node separately:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = new ListNode();
        ListNode even = new ListNode();
        
        ListNode p = head;
        ListNode po = odd;
        ListNode pe = even;
        
        int count = 1;
        
        while (p != null) {
            if (count++ % 2 == 1) {
                po.next = p;
                po = po.next;
            } else {
                pe.next = p;
                pe = pe.next;
            }
            
            p = p.next;
        }
        
        po.next = even.next;
        pe.next = null;
        
        return odd.next;
    }
}

Edited on 12/01/2021. Replaced with iterative solution.

[LeetCode] 237. Delete Node in a Linked List

Problem : https://leetcode.com/problems/delete-node-in-a-linked-list/submissions/

Replace value and 'next' reference with the ones of next node.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        
        node.val = node.next.val
        node.next = node.next.next

[LeetCode] 234. Palindrome Linked List

Problem : https://leetcode.com/problems/palindrome-linked-list/

Use post-order traversal to check the input string recursively.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        left = 0
        
        def postorder(node, right):
            nonlocal head
            nonlocal left
            
            if node:
                tmp = postorder(node.next, right + 1)
                if not tmp:
                    return tmp
                
                if left < right:
                    if node.val != head.val:
                        return False
                
                    head = head.next
                    left += 1
                
                return True
                
            return True
        
        return postorder(head, 0)

[LeetCode] 206. Reverse Linked List

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

The recursive solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            # do not reverse empty list or single element list
            return head
        
        # reverse list starts with the tail element
        tail = head.next
        new_head = self.reverseList(tail)
        
        # append the previous head to the tail
        tail.next = head
        head.next = None
        
        # return the new head
        return new_head

The iterative solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return None
        
        pre = head
        cur = head.next
        
        while cur:
            t = cur.next
            
            cur.next = pre
            pre = cur
            cur = t
        
        head.next = None
        return pre

Edited on 09/07/2021. Add the iterative solution.

[LeetCode] 203. Remove Linked List Elements

Problem : https://leetcode.com/problems/remove-linked-list-elements/

Remove element recursively.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head:
            return head
        
        if head.val == val:
            # remove element with the target val
            return self.removeElements(head.next, val)
        
        head.next = self.removeElements(head.next, val)
        
        return head

[LeetCode] 160. Intersection of Two Linked Lists

Problem : https://leetcode.com/problems/intersection-of-two-linked-lists/

Hash table based solution:

Time Complexity = O ( M + N )

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        
        memo = set()

        p1 = headA
        p2 = headB

        while p1:
            memo.add(p1)
            p1 = p1.next

        while p2:
            if p2 in memo:
                return p2

            p2 = p2.next

        return None

[LeetCode] 148. Sort List

Problem : https://leetcode.com/problems/sort-list/

Use merge sort to get O( n log n ) time complexity.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
              
        # divide into 2 parts
        fast, slow = head, head
        
        while fast and fast.next:
            fast = fast.next.next
            if fast:
                slow = slow.next
            
        tmp = slow.next
        slow.next = None

        left = self.sortList(head)
        right = self.sortList(tmp)

        return self.merge(left, right)
    
    def merge(self, left, right):
        dummy = ListNode(0)
        p = dummy
        
        while left and right:
            if left.val <= right.val:
                p.next = left
                p = p.next
                left = left.next
            else:
                p.next = right
                p = p.next
                right = right.next
        
        while left:
            p.next = left
            p = p.next
            left = left.next
        
        while right:
            p.next = right
            p = p.next
            right = right.next
        
        p.next = None
        
        return dummy.next

[LeetCode] 147. Insertion Sort List

Problem : https://leetcode.com/problems/insertion-sort-list/

Time Complexity = O ( N ** 2 ),  N = length of input list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode();
        
        ListNode p = head;
        ListNode pre;
        ListNode cur;
        
        while (p != null) {
            pre = dummy;
            cur = dummy.next;
            
            while (cur != null && cur.val <= p.val) {
                pre = cur;
                cur = cur.next;
            }
            
            ListNode tmp = p.next;
            
            pre.next = p;
            p.next = cur;
            p = tmp;
        }
        
        return dummy.next;
    }
}

Edited on 12/14/2021. Replace with Java implementation.

[LeetCode] 146. LRU Cache

Problem : https://leetcode.com/problems/lru-cache/

Use doubly linked list to save order of inserted value node.

Most recently used node is on the tail of the doubly linked list.

Least recently used node is no the head of the doubly linked list.

Use dictionary to save the added value and its related linked list node.

Time complexity  = O ( 1 )

class Node:
    def __init__(self, key):
        self.pre = None
        self.next = None
        self.key = key

class LRUCache:
    def __init__(self, capacity: int):
        self.memo = {}
        self.queue = Node(-1)
        self.tail = self.queue
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.memo:
            val, node = self.memo[key]
            
            self._remove(node)
            self._append(node)

            return val
        
        return -1
        
    def put(self, key: int, value: int) -> None:
        if key in self.memo:
            _, node = self.memo[key]
         
            self.memo[key] = (value, node)
            self._remove(node)
            self._append(node)
        elif len(self.memo) < self.capacity:
            node = Node(key)
            self.memo[key] = (value, node)
            self._append(node)
        else:
            removed = self._popleft()
            del self.memo[removed.key]
            
            node = Node(key)
            self.memo[key] = (value, node)
            self._append(node)
    
    def _remove(self, node):
        if node == self.tail:
            self.tail = node.pre
        
        pre_node = node.pre
        next_node = node.next
        
        pre_node.next = next_node
        if next_node:
            next_node.pre = pre_node
            
    def _append(self, node):
        self.tail.next = node
        node.pre = self.tail
        node.next = None
        
        self.tail = node
    
    def _popleft(self):
        node = self.queue.next
        if node:
            self.queue.next = node.next
            if node.next:
                node.next.pre = self.queue
            
            if self.tail == node:
                self.tail = node.pre
        
        return node


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

[LeetCode] 143. Reorder List

Problem : https://leetcode.com/problems/reorder-list/

Construct the needed list by doing preorder and postorder traversal at the same time.

Time Complexity = O ( N )

Space Complexity =  O ( 1 ) 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        
        self.dummy = ListNode()
        self.p = self.dummy
        
        self.preorder = head
        self.seen = set()
        
        def postorder(node):
            if node:
                postorder(node.next)
                
                # add node by preorder traversal
                if self.preorder not in self.seen:
                    self.seen.add(self.preorder)
                    
                    self.p.next = self.preorder
                    self.preorder = self.preorder.next

                    self.p = self.p.next
                
                # add node by postorder traversal
                if node not in self.seen:
                    self.seen.add(node)
                    
                    self.p.next = node
                    self.p = self.p.next
        
        postorder(head)
        
		# end the list
        self.p.next = None

A stack based solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head: return
        
        stack = []
        
        p = head
        total = 0
        
        while p:
            stack.append(p)
            p = p.next
            total += 1
        
        total = total // 2
        
        p = head
        while total > 0:
            tmp = p.next
            p.next = stack.pop()
            total -= 1
            
            p = p.next
            p.next = tmp
            p = p.next
            
        
        p.next = None

An iterative solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode p1 = head;  // slow
        ListNode p2 = head;  // fast
        
        // find the middle node
        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        
        ListNode mid = p1.next;
        p1.next = null;
        
        // return directly if the second half list is empty
        if (mid == null) {
            return;
        }
        
        // reverse the second half list
        ListNode pre = null;
        ListNode cur = mid;
        
        while (cur.next != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        cur.next = pre;
        
        // reorder the list
        p1 = head;
        p2 = cur;
        
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        
        while (p1 != null || p2 != null) {
            
            if (p1 != null) {
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            }
            
            if (p2 != null) {
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
    }
}

Edited on 12/21/2021. Add the iterative solution.

[LeetCode] 142. Linked List Cycle II

Problem : https://leetcode.com/problems/linked-list-cycle-ii/

Hash table based solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        memo = set()
        
        while head:
            if head in memo:
                return head
            
            memo.add(head)
            head = head.next
            
        return head

Fast and slow pointer solution:

Space complexity = O ( 1 )

Firstly, pointer P1 moves 2 times faster than P2. The linked list has cycle if P1 meets P2

Assume P1 and P2 meet at node P. Because P1 moves 2 times faster P2, A + B + C + B = 2 * (A + B)

So A = C.

Secondly, move pointer P1 back to the head of linked list. Then move P1 and P2 with same speed. P1 and P2 must meet again at node Q which is the node where the cycle starts.

      Q       P

--A---|---B---|
      |       |
      |       |
      |       |
      |---C---|

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
     
        p1 = p2 = head
        
        while p1 and p1.next and p2:
            p1 = p1.next.next
            p2 = p2.next
            
            if p1 == p2:
                # find the cycle
                p1 = head
                
                while p1 != p2:
                    p1 = p1.next
                    p2 = p2.next
                
                return p1
        
        
        return None

[LeetCode] 141. Linked List Cycle

Problem : https://leetcode.com/problems/linked-list-cycle/

Hash set based solution:

Time Complexity = O( N )

Space Complexity = O( N )

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        p = head
        memo = set()
        
        while p:
            if p in memo:
                return True
            else:
                memo.add(p)
                p = p.next
      

        return False

Fast and slow pointer solution:

Iterate the list with 'fast' and 'slow' pointers. If 'fast' pointer encounter 'slow' pointer, it means there is a cycle in the linked list.

Time Complexity = O ( N )

Space Complexity = O ( 1 )

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fast, slow = head, head
        
        while fast and fast.next:
            if fast.next == slow:
                return True
            
            # 'fast' moves forward 2 steps
            fast = fast.next.next
            
            # 'slow' moves forward 1 step
            slow = slow.next
        
        return False

[LeetCode] 138. Copy List with Random Pointer

Problem : https://leetcode.com/problems/copy-list-with-random-pointer/

Use dictionary to map the original node to its copy.

Recursive solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        copies = {}
        
        def copy(node):
            if not node:
                return None
            
            copied = None
            if node in copies:
                return copies[node]
           
            copied = Node(node.val)
            copies[node] = copied
                
            copied.next = copy(node.next)
            copied.random = copy(node.random)
            
            return copied
        
        return copy(head)

Iterative solution:

Step1, create copy of each node and save the mapping relationship from each node to its copies.

Step2,  re-link each node's random pointer

"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        
        copies = dict()
        
        dummy = Node(0)
        
        p1 = dummy
        p2 = head
        
        while p2:
            p1.next = Node(p2.val)
            copies[p2] = p1.next
            
            p1 = p1.next
            p2 = p2.next
            
        
        p1 = dummy.next
        p2 = head
        while p1:
            if p2.random:
                p1.random = copies[p2.random]
                
            p1 = p1.next
            p2 = p2.next
            
        
        return dummy.next

[LeetCode] 109. Convert Sorted List to Binary Search Tree

Problem : https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

Use fast-slow pointer to find mid node of the given linked list.

Then create BST recursively.

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;

        ListNode mid = breakInMiddle(head);

        return new TreeNode(
            mid.val,
            sortedListToBST(head != mid ? head : null),
            sortedListToBST(mid.next));
    }

    ListNode breakInMiddle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }

        if (pre != null) pre.next = null;
        return slow;
    }
}

[LeetCode] 92. Reverse Linked List II

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

Not really difficult. Be careful that the index starts from 1.  And it requires to reverse the list in range [m ~ n].

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        dummy = ListNode()
        p = dummy
              
        def helper(i, node):
            if not node:
                return node
            
            nonlocal p
            
            if i < m:
                # append current node keep list order
                p.next = node
                p = p.next
                return helper(i+1, node.next)
            elif i > n:
                # return rest of the list
                return node
            else:
                # reverse order with postorder traversal
                tail = helper(i+1,node.next)
                p.next = node
                p = p.next
                
                return tail
        
        # append rest of the list
        p.next = helper(1, head)
        
        return dummy.next

An iterative solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        dummy1 = ListNode() # the prefix list in original order
        dummy2 = ListNode() # reversed list
        
        p1 = dummy1
        p2 = dummy2
        p3 = None    # end of the reversed list
         
        while right >= 0:
            left -= 1
            right -= 1
            
            if left > 0:
                p1.next = head
                p1 = p1.next
                head = head.next
                continue
                
            if left <= 0 and right >= 0:
                if left == 0:
                    p3 = head
                    
                tmp = head
                head = head.next
                
                tmp.next = p2.next
                p2.next = tmp
                continue
            
        p1.next = p2.next
        p3.next = head
        
        return dummy1.next