SUBTRACT

08 Nov 2018 in Programming on Linked list, Interview, Python

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

1st node’s new value = the last node’s value - first node’s current value 2nd node’s new value = the second last node’s value - 2nd node’s current value, and so on …

NOTE : If the length L of linked list is odd, then the first half implies at first floor(L/2) nodes. So, if L = 5, the first half refers to first 2 nodes. If the length L of linked list is even, then the first half implies at first L/2 nodes. So, if L = 4, the first half refers to first 2 nodes. Example :

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.

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

class Solution:
    # @param A : head node of linked list
    # @return the head node in the linked list
    def subtract(self, A):
        list_len = 0
        node = A
        while(node):
            list_len += 1
            node = node.next
        if list_len < 2: return A
        half = list_len // 2
        curr_node = A
        i = 1
        while i <= half:
            curr = i
            trg = list_len - i + 1
            node = curr_node
            while curr < trg:
                node = node.next
                curr += 1
                
            curr_node.val = node.val - curr_node.val
            i += 1
            curr_node = curr_node.next
        return A

List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Try solving it using constant additional space.

Example :

Input : 

                  ______
                 |     |
                 \/    |
        1 -> 2 -> 3 -> 4

Return the node corresponding to node 3. 

Hint: We travel through the list and keep track of the visited node (can use set or hash table). If we meet a visited node, output the node.

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

class Solution:
    # @param A : head node of linked list
    # @return the first node in the cycle in the linked list
    def detectCycle(self, A):
        
        visited = set()
        node = A
        while node:
            if node in visited:
                return node
            else:
                visited.add(node)
                node = node.next
        return None