在go语言中实现对两个有序链表的相同元素删除算法示例

Go  /  管理员 发布于 2年前   473

给出两条有序的链表，实现删除两条链表中共有的元素的算法，最终返回两个结果链表。

比如：

输入:

1->3->6->9
1->2->6->10

输出:

3->9
2->10

解决思路：

使用双指针(p1,p2)同时遍历两条链表，碰到相同大小的节点就同时移除，不相同的则移动较小值的指针。

这里注意一定要用空节点(pre节点)指向头节点，用于最终返回结果以及删除节点。

下面是我的实现代码，欢迎大家给出其他解法以及优雅的写法：

type Node struct {
    value int
    next *Node
}
func RemoveCommonItems(head1 Node, head2 Node) (Node, Node){
    p1, p2 := new(Node), new(Node)
    p1.next = &head1
    p2.next = &head2
    pre1 := p1
    pre2 := p2
    for p1.next != nil && p2.next != nil {
        if p1.next.value == p2.next.value {
            p1.next = p1.next.next
            p2.next = p2.next.next
        } else if p1.next.value > p2.next.value {
            p2 = p2.next
        } else {
            p1 = p1.next
        }
    }
    return *pre1.next, *pre2.next
}

代码测试:

package main
import "fmt"
//创建链表
func createLinkList(values []int) Node {
   pre := new(Node)
   p := pre
   for _, value := range values {
      p.next = new(Node)
      p.next.value = value
      p = p.next
   }
   return *pre.next
}
//打印链表
func printLinkList(head *Node) {
   for head != nil {
      fmt.Printf("%d -> ", head.value)
      head = head.next
   }
   fmt.Println("")
}
func main() {
   head1 := createLinkList([]int{1,3,6,9})
   head2 := createLinkList([]int{1,2,6,10})
   printLinkList(&head1)
   printLinkList(&head2)
   head1, head2 = RemoveCommonItems(head1, head2)
   printLinkList(&head1)
   printLinkList(&head2)
}

输出：

1 -> 3 -> 6 -> 9 -> 
1 -> 2 -> 6 -> 10 -> 
3 -> 9 -> 
2 -> 10 ->