Added 8 linked list solutions

varunu28 · varunu28 · commit 4b4194a8aae7 · 2017-10-16T16:15:08.000-07:00
diff --git a/Medium/Convert Sorted List to Binary Search Tree.java b/Medium/Convert Sorted List to Binary Search Tree.java
@@ -0,0 +1,46 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    ListNode curr;
+    
+    public TreeNode sortedListToBST(ListNode head) {        
+        curr = head;
+        return generate(count(head));
+    }
+    
+    public int count(ListNode node) {
+        int n = 0;
+        while (node != null) {
+            node = node.next;
+            ++n;
+        }
+        return n;
+    }
+    
+    public TreeNode generate(int n) {
+        if (n==0) return null;
+        
+        TreeNode node = new TreeNode(0);
+        node.left = generate(n/2);
+        node.val = curr.val;
+        curr = curr.next;
+        node.right = generate(n-(n/2)-1);
+        
+        return node;
+    }
+}
diff --git a/Medium/Copy List with Random Pointer.java b/Medium/Copy List with Random Pointer.java
@@ -0,0 +1,29 @@
+/**
+ * Definition for singly-linked list with a random pointer.
+ * class RandomListNode {
+ *     int label;
+ *     RandomListNode next, random;
+ *     RandomListNode(int x) { this.label = x; }
+ * };
+ */
+public class Solution {
+    public RandomListNode copyRandomList(RandomListNode head) {
+        if (head == null) return head;
+        
+        Map<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
+        
+        RandomListNode curr = head;
+        while (curr != null) {
+            map.put(curr,new RandomListNode(curr.label));
+            curr = curr.next;
+        }
+        
+        for (Map.Entry<RandomListNode, RandomListNode> entry : map.entrySet()) {
+            RandomListNode n = entry.getValue();
+            n.next = map.get(entry.getKey().next);
+            n.random = map.get(entry.getKey().random);
+        }
+        
+        return map.get(head);
+    }
+}
diff --git a/Medium/Insertion Sort List.java b/Medium/Insertion Sort List.java
@@ -0,0 +1,29 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode insertionSortList(ListNode head) {
+        ListNode temp = head;
+        while (temp != null) {
+            ListNode curr =temp;
+            int v = curr.val;
+            ListNode t = temp;
+            while (curr != null) {
+                if (curr.val < v) {
+                    v = curr.val;
+                    t = curr;
+                }
+                curr = curr.next;
+            }
+            t.val = temp.val;
+            temp.val = v;
+            temp = temp.next;
+        }
+        return head;
+    }
+}
diff --git a/Medium/Partition List.java b/Medium/Partition List.java
@@ -0,0 +1,37 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode partition(ListNode head, int x) {
+        Queue<Integer> small = new LinkedList<>();
+        Queue<Integer> bigOrEqual = new LinkedList<>();
+        ListNode curr = head;
+        while (curr != null){
+            if (curr.val < x) {
+                small.add(curr.val);
+            }
+            else {
+                bigOrEqual.add(curr.val);
+            }
+            curr = curr.next;
+        }
+        
+        curr = head;
+        while (curr != null) {
+            if (!small.isEmpty()) {
+                curr.val = small.remove();
+            }
+            else {
+                curr.val = bigOrEqual.remove();
+            }
+            curr = curr.next;
+        }
+        
+        return head;
+    }
+}
diff --git a/Medium/Remove Duplicates from Sorted List II.java b/Medium/Remove Duplicates from Sorted List II.java
@@ -0,0 +1,32 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode deleteDuplicates(ListNode head) {
+        if(head==null) return null;
+        
+        ListNode FakeHead=new ListNode(0);
+        FakeHead.next=head;
+        ListNode pre=FakeHead;
+        ListNode cur=head;
+        
+        while(cur!=null){
+            while(cur.next!=null&&cur.val==cur.next.val){
+                cur=cur.next;
+            }
+            if(pre.next==cur){
+                pre=pre.next;
+            }
+            else{
+                pre.next=cur.next;
+            }
+            cur=cur.next;
+        }
+        return FakeHead.next;
+    }
+}
diff --git a/Medium/Reorder List.java b/Medium/Reorder List.java
@@ -0,0 +1,36 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public void reorderList(ListNode head) {
+        if (head == null || head.next == null) return;
+        ArrayList<Integer> arr = new ArrayList<>();
+        ListNode temp = head;
+        while(temp != null) {
+            arr.add(temp.val);
+            temp = temp.next;
+        }
+        
+        temp = head;
+        int i=0;
+        int j=arr.size()-1;
+        while (temp != null) {
+            temp.val = arr.get(i);
+            if (temp.next != null) {
+                temp.next.val = arr.get(j);
+                temp = temp.next.next;
+            }
+            else {
+                temp = temp.next;
+            }
+            i++;
+            j--;
+            
+        }
+    }
+}
diff --git a/Medium/Reverse Linked List II.java b/Medium/Reverse Linked List II.java
@@ -0,0 +1,31 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode reverseBetween(ListNode head, int m, int n) {
+        ArrayList<Integer> arr = new ArrayList<>();
+        ListNode curr = head;
+        while (curr != null) {
+            arr.add(curr.val);
+            curr = curr.next;
+        }
+        
+        curr = head;
+        int i=1;
+        int j=n-1;
+        while(curr != null) {
+            if (i>=m && i<=n) {
+                curr.val = arr.get(j);
+                j--;
+            }
+            curr = curr.next;
+            i++;
+        }
+        return head;
+    }
+}
diff --git a/Medium/Reverse Nodes in k-group.java b/Medium/Reverse Nodes in k-group.java
@@ -0,0 +1,32 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode reverseKGroup(ListNode head, int k) {
+        ArrayList<Integer> arr = new ArrayList<>();
+        ListNode curr = head;
+        while (curr != null) {
+            arr.add(curr.val);
+            curr = curr.next;
+        }
+        
+        curr = head;
+        int i = 0;
+        int n = k;
+        while(i+k <= arr.size()) {
+            while(n != 0) {
+                curr.val = arr.get(i+n-1);
+                curr = curr.next;
+                n--;
+            }
+            i += k;
+            n = k;
+        }
+        return head;
+    }
+}
