Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example 1: Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULL Example 2: Input: 2->1->3->5->6->4->7->NULL Output: 2->3->6->7->1->5->4->NULL Note: The relative order inside both the even and odd groups should remain as it was in the input.

by lek tin in "algorithm" access_time 2-min read

Insertion Sort List

Algorithm of Insertion Sort Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. Example 1 Input: 4->2->1->3 Output: 1->2->3->4 Example 2 Input: -1->5->3->4->0 Output: -1->0->3->4->5 Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.

by lek tin in "algorithm" access_time 1-min read

Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node. Example 1 Input: [1,2,3,4,5] Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judge's serialization of this node is [3,4,5]). Note that we returned a ListNode object ans, such that: ans.val = 3, ans.next.val = 4, ans.

by lek tin in "algorithm" access_time 1-min read

Sort List

Sort a linked list in O(n log n) time using constant space complexity. Example 1 Input: 4->2->1->3 Output: 1->2->3->4 Example 2 Input: -1->5->3->4->0 Output: -1->0->3->4->5 Solution (merge sort - top down) Time: O(NlogN) Space: O(logN) Doesn’t satisfy the requirement # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def sortList(self, head: ListNode) -> ListNode: if not head or not head.

by lek tin in "algorithm" access_time 2-min read

Design Circular Deque

Design your implementation of the circular double-ended queue (deque). Your implementation should support following operations: MyCircularDeque(k): Constructor, set the size of the deque to be k. insertFront(): Adds an item at the front of Deque. Return true if the operation is successful. insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful. deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.

by lek tin in "algorithm" access_time 3-min read

Design Circular Queue

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”. One of the benefits of the circular queue is that we can make use of the spaces in front of the queue.

by lek tin in "algorithm" access_time 3-min read

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome. Example 1 Input: 1->2 Output: false Example 2 Input: 1->2->2->1 Output: true Follow up: Could you do it in O(n) time and O(1) space? Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def isPalindrome(self, head: ListNode) -> bool: if not head: return True middle = self.

by lek tin in "algorithm" access_time 1-min read

Copy List With Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Solution Solution 1: Insert cloned nodes in between original nodes then connect the cloned nodes # Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.

by lek tin in "algorithm" access_time 2-min read

Reverse Nodes in K Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. Example Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5

by lek tin in "algorithm" access_time 3-min read

Reverse Linked List

Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both? Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head, prev = null, after = new ListNode(0); // null 1 -> 2 -> 3 -> 4 -> 5 -> NULL // prev cur after while (cur !

by lek tin in "algorithm" access_time 2-min read