0%
Theme NexT works best with JavaScript enabled
今天开始 LeetCode 链表 。
707-c1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 class MyLinkedList { private class Node { let val: Int var next: Node ? init (val : Int , next : Node ? = nil ) { self .val = val self .next = next } } private var size: Int private var head: Node ? init () { size = 0 head = Node (val: 0 ) } func get (_ index : Int ) -> Int { guard 0 ..< size ~= index else { return - 1 } var curr = head for _ in 0 ..< index + 1 { curr = curr? .next } return curr! .val } func addAtHead (_ val : Int ) { addAtIndex(0 , val) } func addAtTail (_ val : Int ) { addAtIndex(size, val) } func addAtIndex (_ index : Int , _ val : Int ) { guard 0 ... size ~= index else { return } var pred = head for _ in 0 ..< index { pred = pred? .next } size += 1 let toAdd = Node (val: val) toAdd.next = pred? .next pred? .next = toAdd } func deleteAtIndex (_ index : Int ) { guard 0 ..< size ~= index else { return } var pred = head for _ in 0 ..< index { pred = pred? .next } size -= 1 pred? .next = pred? .next? .next } }
141-e2.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 func hasCycle (_ head : ListNode ?) -> Bool { var fastNode = head var slowNode = head while slowNode != nil , fastNode != nil , fastNode? .next != nil { fastNode = fastNode? .next? .next slowNode = slowNode? .next if fastNode === slowNode { return true } } return false }
142-c2.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 func detectCycle (_ head : ListNode ?) -> ListNode ? { var fastNode = head var slowNode = head while slowNode != nil , fastNode != nil , fastNode? .next != nil { fastNode = fastNode? .next? .next slowNode = slowNode? .next if fastNode === slowNode { var anotherNode = head while anotherNode !== slowNode { anotherNode = anotherNode? .next slowNode = slowNode? .next } return anotherNode } } return nil }
160-e3.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 func getIntersectionNode (_ headA : ListNode ?, _ headB : ListNode ?) -> ListNode ? { var nodeA = headA var nodeB = headB while nodeA !== nodeB { nodeA = nodeA == nil ? headB : nodeA? .next nodeB = nodeB == nil ? headA : nodeB? .next } return nodeA }
19-e2.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 func removeNthFromEnd (_ head : ListNode ?, _ n : Int ) -> ListNode ? { var fastNode = head var slowNode = head for _ in 0 ..< n { fastNode = fastNode? .next } guard fastNode != nil else { return head? .next } while fastNode? .next != nil { fastNode = fastNode? .next slowNode = slowNode? .next } slowNode? .next = slowNode? .next? .next return head }
19-s1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 func removeNthFromEnd (_ head : ListNode ?, _ n : Int ) -> ListNode ? { var fastNode = head var slowNode: ListNode ? var count = n while fastNode != nil { if count <= 0 { slowNode = slowNode == nil ? head : slowNode? .next } fastNode = fastNode? .next count -= 1 } guard slowNode != nil else { return head? .next } slowNode? .next = slowNode? .next? .next return head }
206-e1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 func reverseList (_ head : ListNode ?) -> ListNode ? { var newHead: ListNode ? var currentNode = head while currentNode != nil { let tempNode = currentNode? .next currentNode? .next = newHead newHead = currentNode currentNode = tempNode } return newHead }
203-c1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 func removeElements (_ head : ListNode ?, _ val : Int ) -> ListNode ? { let sentinelHead: ListNode ? = ListNode (0 ) sentinelHead? .next = head var previousNode = sentinelHead var currentNode = head while currentNode != nil { if currentNode? .val == val { previousNode? .next = currentNode? .next } else { previousNode = currentNode } currentNode = currentNode? .next } return sentinelHead? .next }
328-e1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 func oddEvenList (_ head : ListNode ?) -> ListNode ? { var oddNode = head var evenNode = head? .next let evenHead = evenNode while evenNode != nil , evenNode? .next != nil { oddNode? .next = evenNode? .next oddNode = oddNode? .next evenNode? .next = oddNode? .next evenNode = evenNode? .next } oddNode? .next = evenHead return head }
234-c1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 func isPalindrome (_ head : ListNode ?) -> Bool { var currentNode = head var nodes = [ListNode ]() while currentNode != nil { nodes.append(currentNode! ) currentNode = currentNode? .next } var leftIndex = nodes.startIndex var rightIndex = nodes.index(before: nodes.endIndex) while leftIndex < rightIndex { guard nodes[leftIndex].val == nodes[rightIndex].val else { return false } nodes.formIndex(after: & leftIndex) nodes.formIndex(before: & rightIndex) } return true }
707-c2.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 class MyLinkedList { private class Node { let val: Int var prev: Node ? var next: Node ? init (val : Int , prev : Node ? = nil , next : Node ? = nil ) { self .val = val self .prev = prev self .next = next } } private var size: Int private var head: Node ? private var tail: Node ? init () { size = 0 head = Node (val: 0 ) tail = Node (val: 0 ) head? .next = tail tail? .prev = head } func get (_ index : Int ) -> Int { guard 0 ..< size ~= index else { return - 1 } var curr: Node ? let leftIndex = index + 1 let rightIndex = size - index if leftIndex < rightIndex { curr = head for _ in 0 ..< leftIndex { curr = curr? .next } } else { curr = tail for _ in 0 ..< rightIndex { curr = curr? .prev } } return curr! .val } func addAtHead (_ val : Int ) { addAtIndex(0 , val) } func addAtTail (_ val : Int ) { addAtIndex(size, val) } func addAtIndex (_ index : Int , _ val : Int ) { guard 0 ... size ~= index else { return } var pred: Node ? var succ: Node ? let leftIndex = index let rightIndex = size - index if leftIndex < rightIndex { pred = head for _ in 0 ..< leftIndex { pred = pred? .next } succ = pred? .next } else { succ = tail for _ in 0 ..< rightIndex { succ = succ? .prev } pred = succ? .prev } size += 1 let toAdd = Node (val: val) toAdd.prev = pred toAdd.next = succ pred? .next = toAdd succ? .prev = toAdd } func deleteAtIndex (_ index : Int ) { guard 0 ..< size ~= index else { return } var pred: Node ? var succ: Node ? let leftIndex = index let rightIndex = size - index if leftIndex < rightIndex { pred = head for _ in 0 ..< leftIndex { pred = pred? .next } succ = pred? .next? .next } else { succ = tail for _ in 0 ..< rightIndex - 1 { succ = succ? .prev } pred = succ? .prev? .prev } size -= 1 pred? .next = succ succ? .prev = pred } }
21-c1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 func mergeTwoLists (_ l1 : ListNode ?, _ l2 : ListNode ?) -> ListNode ? { guard let list1 = l1, let list2 = l2 else { return l1 ?? l2 } let list3: ListNode ? if list1.val > list2.val { list3 = list2 list3? .next = mergeTwoLists(list1, list2.next) } else { list3 = list1 list3? .next = mergeTwoLists(list1.next, list2) } return list3 }
21-s1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 func mergeTwoLists (_ l1 : ListNode ?, _ l2 : ListNode ?) -> ListNode ? { guard let list1 = l1, let list2 = l2 else { return l1 ?? l2 } var list3: ListNode ? var node1: ListNode ? = list1 var node2: ListNode ? = list2 var node3: ListNode ? = ListNode (0 ) while node1 != nil , node2 != nil { if node1! .val > node2! .val { node3? .next = node2 node2 = node2? .next } else { node3? .next = node1 node1 = node1? .next } if list3 == nil { list3 = node3? .next } node3 = node3? .next } if node1 != nil { node3? .next = node1 } if node2 != nil { node3? .next = node2 } return list3 }
2-e1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 func addTwoNumbers (_ l1 : ListNode ?, _ l2 : ListNode ?) -> ListNode ? { let list3: ListNode ? = ListNode (0 ) var node1 = l1 var node2 = l2 var node3 = list3 var quotient: Int = 0 var remainder: Int = 0 while node1 != nil || node2 != nil { let sum = (node1? .val ?? 0 ) + (node2? .val ?? 0 ) + quotient (quotient, remainder) = sum.quotientAndRemainder(dividingBy: 10 ) node3? .next = ListNode (remainder) node1 = node1? .next node2 = node2? .next node3 = node3? .next } if quotient > 0 { node3? .next = ListNode (quotient) } return list3? .next }
430-s1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 func flatten (_ head : Node ?) -> Node ? { var node = head var stack: [Node ] = [] while node != nil { if let childNode = node? .child { if let nextNode = node? .next { stack.append(nextNode) } node? .next = childNode childNode.prev = node node? .child = nil } else if node? .next == nil { if ! stack.isEmpty { let previousNode = stack.removeLast() node? .next = previousNode previousNode.prev = node } } node = node? .next } return head }
138-c3.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 func copyRandomList (_ head : Node ?) -> Node ? { var node = head while node != nil { let nextNode = Node (node! .val) nextNode.next = node? .next node? .next = nextNode node = nextNode.next } node = head while node != nil { node? .next? .random = node? .random? .next node = node? .next? .next } var oldNode = head var newNode = head? .next let newHead = newNode while oldNode != nil { oldNode? .next = oldNode? .next? .next newNode? .next = newNode? .next? .next oldNode = oldNode? .next newNode = newNode? .next } return newHead }
61-c1.swift view raw 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 func rotateRight (_ head : ListNode ?, _ k : Int ) -> ListNode ? { guard k > 0 else { return head } var count = 1 var node = head while node? .next != nil { count += 1 node = node? .next } var addCount = count - k % count node? .next = head while addCount > 0 { node = node? .next addCount -= 1 } let newHead = node? .next node? .next = nil return newHead }