Skip to content

Instantly share code, notes, and snippets.

@nhatlee
Last active February 13, 2019 10:59
Show Gist options
  • Save nhatlee/462d9b1511ced31a50693ac41f160b50 to your computer and use it in GitHub Desktop.
Save nhatlee/462d9b1511ced31a50693ac41f160b50 to your computer and use it in GitHub Desktop.
Linkedlist Recursive Reverse
class Node {
var data: Int
var next: Node?
// init(_ data: Int) {
// self.data = data
// }
init?(_ values: Array<Int>) {
var valuesCopy = values
if valuesCopy.count == 0 {
return nil
}
data = valuesCopy.removeFirst()
next = Node(Array(valuesCopy))
}
public var description: String {
var desc = String()
var listRef : Node? = self
while listRef != nil {
desc += "\((listRef?.data)!) "
listRef = listRef?.next
}
return desc
}
}
extension Node {
func reverse() -> Node?{
// Iterate through each item, and reverse its link until you visit the last node in the list.
// Once you reach the end, All items except the last one would have
// their links reversed.
var nextNode : Node? = self.next
var prevNode : Node? = nil
var currentNode : Node? = self
while nextNode != nil{
currentNode?.next = prevNode
prevNode = currentNode
currentNode = nextNode
nextNode = currentNode?.next
}
//Ensure the last item in the list too has its links reversed.
currentNode?.next = prevNode
return currentNode
}
}
private(set) var head: Node?
var last: Node? {
guard var node = head else {
return nil
}
while let next = node.next {
node = next
}
return node
}
func recursiveReverse(list:Node?) -> Node? {
return list?.reverse()
}
let node = Node([1,3,5,6,11,45])
print(node?.description)
///--------->>>>>>>>>>>>>>>>>>>>>Another good solution:
//func recursiveReverse(list: Node?) -> Node? {
// guard let list = list else { return nil }
// guard let next = list.next else { return list }
//
// list.next = nil // Unlink to prevent cycles
// let reversed = recursiveReverse(list: next)
// next.next = list // Re-attach
//
// return reversed
//}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment