Last active
October 8, 2020 20:11
-
-
Save SandeepAggarwal/65824bd293ab92b4ff6a201304bfbf9f to your computer and use it in GitHub Desktop.
Linked List in place merged of two sorted lists
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import UIKit | |
import PlaygroundSupport | |
class Node { | |
var data: Int | |
var next: Node? | |
init(data: Int) { | |
self.data = data | |
} | |
} | |
class LinkedList { | |
var head: Node? | |
init(head: Node?) { | |
self.head = head | |
} | |
func printList() { | |
print("list is: ") | |
var node: Node? = head | |
while let current = node { | |
print(current.data) | |
node = current.next | |
} | |
} | |
static func mergeList(ll1: LinkedList?, ll2: LinkedList?) -> LinkedList? { | |
var h1 = ll1?.head | |
var h2 = ll2?.head | |
guard h1 != nil else { | |
return LinkedList(head: h2) | |
} | |
guard h2 != nil else { | |
return LinkedList(head: h1) | |
} | |
let head: Node? | |
var prev: Node? | |
if (h1?.data ?? 0) < (h2?.data ?? 0) { | |
head = h1 | |
h1 = h1?.next | |
} else { | |
head = h2 | |
h2 = h2?.next | |
} | |
prev = head | |
while h1 != nil && h2 != nil { | |
if (h1?.data ?? 0) < (h2?.data ?? 0) { | |
prev?.next = h1 | |
prev = h1 | |
h1 = h1?.next | |
} else { | |
prev?.next = h2 | |
prev = h2 | |
h2 = h2?.next | |
} | |
if h1 == nil { | |
prev?.next = h2 | |
} | |
if h2 == nil { | |
prev?.next = h1 | |
} | |
} | |
return LinkedList(head: head) | |
} | |
} | |
let node1 = Node(data: 1) | |
let node3 = Node(data: 3) | |
let node5 = Node(data: 5) | |
node1.next = node3 | |
node3.next = node5 | |
let ll1 = LinkedList(head: node1) | |
ll1.printList() | |
let node2 = Node(data: 2) | |
let node4 = Node(data: 4) | |
let node7 = Node(data: 7) | |
let node10 = Node(data: 10) | |
node2.next = node4 | |
node4.next = node7 | |
node7.next = node10 | |
let ll2 = LinkedList(head: node2) | |
ll2.printList() | |
let mergedList = LinkedList.mergeList(ll1: ll1, ll2: ll2) | |
mergedList?.printList() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment