Skip to content

Instantly share code, notes, and snippets.

@SandeepAggarwal
Last active October 8, 2020 20:11
Show Gist options
  • Save SandeepAggarwal/65824bd293ab92b4ff6a201304bfbf9f to your computer and use it in GitHub Desktop.
Save SandeepAggarwal/65824bd293ab92b4ff6a201304bfbf9f to your computer and use it in GitHub Desktop.
Linked List in place merged of two sorted lists
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