How can two generic linked list in swift can be co

2020-07-23 05:43发布

问题:

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
    }
}

回答1:

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
        }
    }
}


回答2:

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
    }
}