I have a generic linked list and I can check if two linked list are equal if each of the node value are same and are in order.
I have a function which divides linked list in two part and later I want to check two list has same value in it's node.
func divideList(atIndex index:Int) -> (first: LLGeneric<T>?,second: LLGeneric<T>?)
I looking it for my use case where I can check palindrome in linked list after dividing and then comparing ( after reversing one list).
Note: my linked list node is generic something like
class LLGenericNode<T> {
var value: T
var next: LLGenericNode?
weak var previous: LLGenericNode?
init(_ value: T) {
self.value = value
}
}
In order to compare values you have to require that T
is Equatable
:
class LLGenericNode<T: Equatable> {
// ...
}
Then you can implement ==
by comparing the values first.
If the values are equal, the list tails are compared recursively.
extension LLGenericNode: Equatable {
static func ==(lhs: LLGenericNode<T>, rhs: LLGenericNode<T>) -> Bool {
if lhs.value != rhs.value {
return false
}
switch (lhs.next, rhs.next) {
case (nil, nil):
// Both tails are == nil:
return true
case let (lvalue?, rvalue?):
// Both tails are != nil:
return lvalue == rvalue // Recursive call
default:
// One tails is nil and the other isn't:
return false
}
}
}
One-liner solution: It should be enough to define a generic T: Equatable
, making sure on overloading the ==
operator, you compare the current values and the next nodes.
Note that with lhs.next == rhs.next
you'll cover both recursion and nullability in one shot:
class Node <T: Equatable>: Equatable {
static func == (lhs: Node, rhs: Node) -> Bool {
lhs.value == rhs.value && lhs.next == rhs.next
}
}