网站开发有专利吗,深圳网站平台哪家强,珠海市网站建设分站怎么样,网站开发平台选择1 问题 链表实现选择排列中经常会遇到一些问题#xff0c;那么该如何解决它们呢#xff1f; 2 方法 这一类问题的基本都是根据题目给定的条件#xff0c;对链表进行各种组合#xff0c;如#xff1a;基于归并排序思想#xff0c;根据节点的数值#xff0c;合并两个链表那么该如何解决它们呢 2 方法 这一类问题的基本都是根据题目给定的条件对链表进行各种组合如基于归并排序思想根据节点的数值合并两个链表合并两个排序的链表、合并k个已排序的链表根据节点的位置对链表重新排序链表的奇偶重排对两个链表节点的数值相加链表相加(二)) 假设链表中每一个节点的值都在 0 - 9 之间那么链表整体就可以代表一个整数。给定两个这种链表请生成代表两个整数相加值的结果链表。整体思路如题目链表的顺序与加法的顺序是相反的自然的想到两种思路把链表的元素压入栈中借助栈实现对反转链表的元素进行操作直接反转链表由于两种方式都需要新建链表存储两个整数的相加值因此空间复杂度都是o(n)。方法1比2多一个栈的空间但是总的空间复杂度也是o(n)。细节提示加法的10进制的进位。设置进位标志incre每次循环判断 val1 list1.pop(-1)list2.pop(-1)incre。并且在循环结束后需要判断incre是否0如果0需要在链表中增加 代码清单 1 class ListNode: def __init__(self, x): self.val x self.next Noneclass Solution: def addInList(self , head1 , head2 ): # write code here list1 [] while head1: list1.append(head1.val) head1 head1.next list2 [] while head2: list2.append(head2.val) head2 head2.next list3 [] incre 0 while len(list1) and len(list2): val1 list1.pop(-1)list2.pop(-1)incre incre val1/10 val1 val1%10 list3.append(val1) while len(list1): val1 list1.pop(-1)incre incre val1/10 val1 val1%10 list3.append(val1) while len(list2): val1 list2.pop(-1)incre incre val1/10 val1 val1%10 list3.append(val1) if incre0: list3.append(incre) dumpyNode ListNode(-1) pHead dumpyNode while len(list3): pHead.next ListNode(list3.pop(-1)) pHead pHead.next return dumpyNode.next def addInList2(self , head1 , head2 ): cur1 head1 pre None while cur1: next1 cur1.next cur1.next pre pre cur1 cur1 next1 head1 pre cur2 head2 pre2 None while cur2: next2 cur2.next cur2.next pre2 pre2 cur2 cur2 next2 head2 pre2 dumpyNode3 ListNode(-1) pHead dumpyNode3 incre 0 while head1 and head2: val head1.valhead2.valincre incre val/10 val val%10 head ListNode(val) pHead.next head pHead pHead.next head1 head1.next head2 head2.next while head1: val head1.valincre incre val/10 val val%10 head ListNode(val) pHead.next head pHead pHead.next head1 head1.next while head2: val head2.valincre incre val/10 val val%10 head ListNode(val) pHead.next head pHead pHead.next head2 head2.next if incre0: head ListNode(incre) pHead.next head pHead pHead.next pHead dumpyNode3.next cur1 pHead pre None while cur1: next1 cur1.next cur1.next pre pre cur1 cur1 next1 return pre 3 结语 针对数组排序问题提出的解决方法证明该方法是有效的。其实上面的题目的思路都很简单相当于把简单的排序从数组迁移到了链表中。个人认为技巧在于链表节点的生成与穿针引线一般可以使用两个辅助节点定义虚拟节点和游走节点虚拟节点负责返回整个链表游走节点负责穿针引线。以提高算法效率。
