SHARE
TWEET

Untitled

a guest Jun 16th, 2019 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import UIKit
  2.  
  3. //Linked lists are composed of Node(s)
  4. class Node<T> {
  5.     var value: T
  6.     var next: Node?
  7.     weak var prev: Node?
  8.  
  9.     init(value: T) {
  10.         self.value = value
  11.     }
  12. }
  13.  
  14. extension Node: Equatable, Hashable {
  15.     static func == (lhs: Node<T>, rhs: Node<T>) -> Bool {
  16.         return
  17.             lhs.next == rhs.next
  18.     }
  19.  
  20.     func hash(into hasher: inout Hasher) {
  21.         hasher.combine(next)
  22.         hasher.combine(prev)
  23.     }
  24. }
  25.  
  26. class LinkedList<T> {
  27.     var head: Node<T>?
  28.     var tail: Node<T>?
  29.     //starts at 1 because a linked list must have at least 1 node
  30.     var nodeCount = 1
  31.  
  32.     init(head: Node<T>?) {
  33.         self.head = head
  34.     }
  35.  
  36.     func append(node: Node<T>) {
  37.         //check if head exists
  38.         guard head != nil else {
  39.             head = node
  40.             return
  41.         }
  42.         var current = head
  43.         // loop through nodes
  44.         while let _ = current?.next {
  45.             //set current to next node
  46.             current = current?.next
  47.         }
  48.         node.prev = current
  49.         current?.next = node
  50.         //set last node's `next` to given node
  51.         tail = node
  52.         nodeCount += 1
  53.     }
  54.  
  55.     func removeNode(node: Node<T>) {
  56.         let prev = node.prev
  57.         let next = node.next
  58.  
  59.         next?.prev = prev
  60.         prev?.next = next
  61.  
  62.         // if head node being removed
  63.         if prev == nil {
  64.             head = next
  65.         }
  66.     }
  67.  
  68.     func insertNode(node: Node<T>, position: Int) {
  69.         var currentNode = head
  70.         var currentPosition = 0
  71.  
  72.         //loop through nodes, starts at head node
  73.         while let _ = currentNode?.next {
  74.             if currentPosition == position {
  75.                 if let prevNode = currentNode?.prev {
  76.                     currentNode?.prev = node
  77.                     prevNode.next = node
  78.                     node.next = currentNode
  79.                 } else {
  80.                     //if head node
  81.                     currentNode?.prev = node
  82.                     node.next = currentNode
  83.                     head = node
  84.                 }
  85.                 return
  86.             }
  87.             currentNode = currentNode?.next
  88.             currentPosition += 1
  89.             // nothing happens if requested position doesn't exist in Linked list
  90.         }
  91.     }
  92. }
  93.  
  94. //1,2,3
  95. let node0 = Node(value: 0)
  96. let node1 = Node(value: 1)
  97. let node2 = Node(value: 2)
  98. let node3 = Node(value: 3)
  99.  
  100. let linkedList = LinkedList(head: node0)
  101. linkedList.append(node: node1)
  102. linkedList.append(node: node2)
  103. linkedList.append(node: node3)
  104. linkedList.append(node: Node.init(value: 5))
  105. linkedList.append(node: Node.init(value: 8))
  106. linkedList.append(node: Node.init(value: 8))
  107. linkedList.append(node: Node.init(value: 8))
  108. linkedList.append(node: Node.init(value: 9))
  109. //linkedList.removeNode(node: node0)
  110. //linkedList.insertNode(node: Node(value: 7), position: 1)
  111.  
  112. //2.1
  113. //Remove Dups: Write code to remove duplicates from an unsorted linked list.
  114. func removeDupes(LL: LinkedList<Int>) -> LinkedList<Int> {
  115.     let linkedList = LL
  116.     var storedInts = Set<Int>()
  117.     var currentNode = linkedList.head
  118.  
  119.     while let _ = currentNode {
  120.         guard let unwrappedCurrentNode = currentNode else {
  121.             return linkedList
  122.         }
  123.  
  124.         if !storedInts.contains(unwrappedCurrentNode.value) {
  125.             storedInts.insert(unwrappedCurrentNode.value)
  126.         } else {
  127.             // remove duplicate node
  128.             linkedList.removeNode(node: unwrappedCurrentNode)
  129.         }
  130.         currentNode = currentNode?.next
  131.     }
  132.     // for visualizing purposes
  133.     dump(linkedList)
  134.     return linkedList
  135. }// loop through 1x 0(n^2) w/o req additional memory, loop through whole list each time while checking for value
  136. //removeDupes(LL: linkedList)
  137.  
  138. //Q 2.2
  139. //Return Kth to Last: Implement an algorithm to find the kth to last element of a singly linked list.
  140. //Hints: #8, #25, #47, #67, # 726
  141. func returnKthToLast(linkedList: LinkedList<Int>, position: Int) -> Int? {
  142.     // if position doesn't exist
  143.     if position < 0 || position > (linkedList.nodeCount - 1) {
  144.         return nil
  145.     }
  146.     // negative number or number that is > count
  147.     var currentNode = linkedList.tail
  148.     var currentPosition = 0
  149.     //store currentPosition
  150.     //iterate bacwards till current position == position
  151.     while currentPosition != position {
  152.         currentNode = currentNode?.prev
  153.         currentPosition += 1
  154.     }
  155.     dump(linkedList)
  156.     return currentNode?.value
  157. }
  158. //returnKthToLast(linkedList: linkedList, position: 4)
  159. //returnKthToLast(linkedList: linkedList, position: 0)
  160. //returnKthToLast(linkedList: linkedList, position: 50)
  161. //linkedList.nodeCount
  162.  
  163. //2.5 Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. (2 linked lists are passed in)
  164. //EXAMPLE
  165. //Input: (7-) 1 -) 6) + (5 -) 9 -) 2).Thatis,617 + 295. Output: 2 -) 1 -) 9.That is, 912.
  166.  
  167. func sumList(linkedList1: LinkedList<Int>, linkedList2: LinkedList<Int>) -> LinkedList<Int> {
  168.     var currentNodeLL1 = linkedList1.head
  169.     var currentNodeLL2 = linkedList2.head
  170.     var greaterThan10 = false
  171.     var total = 0
  172.     var newLinkedList = LinkedList<Int>(head: nil)
  173.  
  174.     //iterate through both linked lists
  175.     while let _ = currentNodeLL1, let _ = currentNodeLL2 {
  176.         total = (currentNodeLL1?.value ?? 0) + (currentNodeLL2?.value ?? 0) + (greaterThan10 ? 1 : 0)
  177.  
  178.         if total >= 10 {
  179.             greaterThan10 = true
  180.             total = total % 10
  181.         } else {
  182.             greaterThan10 = false
  183.         }
  184.         //create new node with each total
  185.         let node = Node(value: total)
  186.         if newLinkedList.head == nil {
  187.             newLinkedList.head = node
  188.         } else {
  189.             newLinkedList.append(node: node)
  190.             if currentNodeLL1 == linkedList1.tail && greaterThan10 {
  191.                 newLinkedList.append(node: Node(value: 1))
  192.             }
  193.         }
  194.         currentNodeLL1 = currentNodeLL1?.next
  195.         currentNodeLL2 = currentNodeLL2?.next
  196.     }
  197.     dump(newLinkedList)
  198.     return newLinkedList
  199. }
  200.  
  201. let sumListNode1 = Node(value: 9)
  202. let sumListNode2 = Node(value: 2)
  203. let sumListNode3 = Node(value: 2)
  204. let sumListNode4 = Node(value: 2)
  205. let sumListNode5 = Node(value: 2)
  206. let sumListNode6 = Node(value: 9)
  207. let sumListTestLL1 = LinkedList(head: sumListNode1)
  208. sumListTestLL1.append(node: sumListNode2)
  209. sumListTestLL1.append(node: sumListNode3)
  210.  
  211. let sumListTestLL2 = LinkedList(head: sumListNode4)
  212. sumListTestLL2.append(node: sumListNode5)
  213. sumListTestLL2.append(node: sumListNode6)
  214.  
  215. //sumList(linkedList1: sumListTestLL1, linkedList2: sumListTestLL2)
  216.  
  217. //2.6 Palindrome: Implement a function to check if a linked list is a palindrome.
  218. //Hints: #5, #13, #29, #61, #101
  219. //input LL
  220. //output Bool
  221. func isLinkedListPalindrome(LL: LinkedList<Int>) -> Bool {
  222.     // reverse LL & compare to the passed in LL
  223.     // store inputCurrentNode
  224.     var currentFrontNode = LL.head
  225.     //store currentReversedNode
  226.     var currentBackNode = LL.tail
  227.     // traverse LL from both ends in opp directions at the same time, input from the head, reversed starting from the tail
  228.     while let _ = currentFrontNode, let _ = currentBackNode{
  229.         // if node value is !=, return false
  230.         if currentFrontNode?.value != currentBackNode?.value {
  231.             return false
  232.         }
  233.         currentFrontNode = currentFrontNode?.next
  234.         currentBackNode = currentBackNode?.prev
  235.     }
  236.     return true
  237. }
  238.  
  239. let palinListNode1 = Node(value: 1)
  240. let palinListNode2 = Node(value: 1)
  241. let palinListNode3 = Node(value: 0)
  242. //let palinListNode4 = Node(value: 1)
  243.  
  244. let palinListTestLL1 = LinkedList(head: palinListNode1)
  245. let palinListTestLL2 = LinkedList(head: palinListNode2)
  246.  
  247. palinListTestLL1.append(node: palinListNode3)
  248. palinListTestLL2.append(node: palinListNode3)
  249. //palinListTestLL1.append(node: palinListNode4)
  250.  
  251. //isLinkedListPalindrome(LL: palinListTestLL1)
  252. palinListTestLL1.head?.next == palinListTestLL2.head?.next
  253.  
  254. //2.7 Intersection: Given two (singly) linked lists, determine if the two lists intersect. Return the inter- secting node. Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.
  255. //Hints: #20, #45, #55, #65, #76, #93, #111, #120, #129
  256.  
  257. func areLinkedListsIntersecting(LL1: LinkedList<Int>, LL2: LinkedList<Int>) -> Node<Int>? {
  258.     //store current nodes in both LL
  259.     var currentLL1Node = LL1.head
  260.     var currentLL2Node = LL2.head
  261.  
  262.     //traverse both LL at the same time
  263.     while let _ = currentLL1Node, let _ = currentLL2Node {
  264.     // if the .next node is the same(made Node class conform to equatable above), return node
  265.         if currentLL1Node?.next == currentLL2Node?.next {
  266.             // for visualizing node value purposes
  267.             dump(currentLL1Node?.next?.value,name:"intersecting node value")
  268.             return currentLL1Node?.next
  269.         }
  270.         currentLL1Node = currentLL1Node?.next
  271.         currentLL2Node = currentLL2Node?.next
  272.     }
  273.     return nil
  274. }
  275. //areLinkedListsIntersecting(LL1: palinListTestLL1, LL2: palinListTestLL2)
  276.  
  277. //2.8 Loop Detection: Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.
  278. //DEFINI TION
  279. //Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
  280. //EXAMPLE
  281. //Input: A -) B -) C -) 0 -) E -) C[the same C as earlier] Output: C
  282. //Hints: #50, #69, #83, #90
  283.  
  284. func loopDetection(LL: LinkedList<Int>) -> Node<Int>? {
  285.     //traverse through list
  286.     // store currentNode
  287.     var currentNode = LL.head
  288.     //set to keep track of what i've seen
  289.     var seenNodes = Set<Node<Int>>()
  290.     while let unwrappedCurrentNode = currentNode { // instead of .next, confirm should cover last node
  291.         // if node.next ! in the set, add it else return the node.next
  292.         if !seenNodes.contains(unwrappedCurrentNode) {
  293.             seenNodes.insert(unwrappedCurrentNode)
  294.         } else {
  295.             return currentNode
  296.         }
  297.         currentNode = currentNode?.next
  298.     }
  299.     return nil
  300. }
  301.  
  302. //loopDetection(LL: palinListTestLL1)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top