SUBTRACT

Given a singly linked list, modify the value of first half nodes such that :

and so on …

Given linked list 1 -> 2 -> 3 -> 4 -> 5,

You should return 4 -> 2 -> 3 -> 4 -> 5
as

for first node, 5 - 1 = 4
for second node, 4 - 2 = 2

Try to solve the problem using constant extra space.

Method:

Reverse second half, modify first half, then reverse second half back and connect first and second half.

Solution:

Time: O(n)
Space: O(1)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    private ListNode reverse(ListNode A) {
        ListNode prev = null;
        ListNode p = A;
        while (p != null) {
            ListNode next = p.next;
            p.next = prev;
            prev = p;
            p = next;
        }
        return prev;
    }
    
    private ListNode findMid(ListNode A) {
        ListNode slow = A;
        ListNode fast = A;
        ListNode mid = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast == null || fast.next == null) {
                mid = slow.next;
                slow.next = null;
                break;
            }
            slow = slow.next;
        }
        return mid;
    }
    
    // 1 -> 2 -> 3 -> 4 -> 5
    // 4 -> 2 -> 3 -> 4 -> 5
    public ListNode subtract(ListNode A) {
        if (A == null || A.next == null) return A;
        ListNode p = A;
        ListNode mid = findMid(A);
        ListNode reverseHead = reverse(mid);
        ListNode reversedP = reverseHead;
        ListNode prev = null;
        while (p != null) {
            p.val = reversedP.val - p.val;
            prev = p;
            p = p.next;
            reversedP = reversedP.next;
        }
        ListNode secondHalfHead = reverse(reverseHead);
        prev.next = secondHalfHead;
        return A;
    }
}