中行软开 11.3编程测评第2题 题解
题干:给定一个单链表,如果链表中相邻的元素相同,则把所有相同的元素相加后合并为一个节点,合并后的节点不需要再次合并。
如2->2->2->6->6,合并完毕之后应是6->12
思路:这道题基本是leetcode-82和leetcode-83的变体,由于题目没有严格的限制,解起来不难,因为完全可以把数据读到临时数组里,处理完再创建个链表返回,这样就避免了容易让人搞迷糊的指针操作。难的是如何原地合并。
代码实现:
class ListNode: def __init__(self, val: int, next_: 'ListNode' = None): self.val = val self.next = next_ def main(head: ListNode): p = head while p: x = p.val while p.next and p.next.val == x: p.val += x p.next = p.next.next p = p.next return head if __name__ == '__main__': ll = ListNode(2, ListNode(2, ListNode(2, ListNode(6, ListNode(6))))) ll = main(ll) while ll: print(ll.val, end=' ') ll = ll.next