Python链表排序相关问题解法

梦里梦外; 2024-02-05 11:29 10阅读 0赞

**1** **问题**

链表实现选择排列中经常会遇到一些问题，那么该如何解决它们呢？

**2** **方法**

这一类问题的基本都是根据题目给定的条件，对链表进行各种组合，如：基于归并排序思想，根据节点的数值，合并两个链表（合并两个排序的链表、合并k个已排序的链表）根据节点的位置，对链表重新排序（链表的奇偶重排）对两个链表节点的数值相加（链表相加(二))

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。  
整体思路，如题目，链表的顺序与加法的顺序是相反的，自然的想到两种思路：把链表的元素压入栈中，借助栈实现对反转链表的元素进行操作；直接反转链表由于两种方式都需要新建链表，存储两个整数的相加值，因此空间复杂度都是o(n)。方法1比2多一个栈的空间，但是总的空间复杂度也是o(n)。细节提示加法的10进制的进位。设置进位标志incre，每次循环判断 val1 = list1.pop(-1)+list2.pop(-1)+incre。并且，在循环结束后，需要判断incre是否>0，如果>0，需要在链表中增加

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td>class ListNode: &nbsp; &nbsp;def __init__(self, x): &nbsp; &nbsp; &nbsp; &nbsp;self.val = x &nbsp; &nbsp; &nbsp; &nbsp;self.next = None class Solution: &nbsp; &nbsp;def addInList(self , head1 , head2 ): &nbsp; &nbsp; &nbsp; &nbsp;# write code here &nbsp; &nbsp; &nbsp; &nbsp;list1 = [] &nbsp; &nbsp; &nbsp; &nbsp;while head1: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;list1.append(head1.val) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head1 = head1.next &nbsp; &nbsp; &nbsp; &nbsp;list2 = [] &nbsp; &nbsp; &nbsp; &nbsp;while head2: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;list2.append(head2.val) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head2 = head2.next &nbsp; &nbsp; &nbsp; &nbsp;list3 = [] &nbsp; &nbsp; &nbsp; &nbsp;incre = 0 &nbsp; &nbsp; &nbsp; &nbsp;while len(list1) and len(list2): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val1 = list1.pop(-1)+list2.pop(-1)+incre &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;incre = val1/10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val1 = val1%10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;list3.append(val1) &nbsp; &nbsp; &nbsp; &nbsp;while len(list1): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val1 = list1.pop(-1)+incre &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;incre = val1/10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val1 = val1%10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;list3.append(val1) &nbsp; &nbsp; &nbsp; &nbsp;while len(list2): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val1 = list2.pop(-1)+incre &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;incre = val1/10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val1 = val1%10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;list3.append(val1) &nbsp; &nbsp; &nbsp; &nbsp;if incre&gt;0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;list3.append(incre) &nbsp; &nbsp; &nbsp; &nbsp;dumpyNode = ListNode(-1) &nbsp; &nbsp; &nbsp; &nbsp;pHead = dumpyNode &nbsp; &nbsp; &nbsp; &nbsp;while len(list3): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead.next = ListNode(list3.pop(-1)) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead = pHead.next &nbsp; &nbsp; &nbsp; &nbsp;return dumpyNode.next &nbsp; &nbsp;def addInList2(self , head1 , head2 ): &nbsp; &nbsp; &nbsp; &nbsp;cur1 = head1 &nbsp; &nbsp; &nbsp; &nbsp;pre = None &nbsp; &nbsp; &nbsp; &nbsp;while cur1: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;next1 = cur1.next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur1.next = pre &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pre = cur1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur1 = next1 &nbsp; &nbsp; &nbsp; &nbsp;head1 = pre &nbsp; &nbsp; &nbsp; &nbsp;cur2 = head2 &nbsp; &nbsp; &nbsp; &nbsp;pre2 = None &nbsp; &nbsp; &nbsp; &nbsp;while cur2: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;next2 = cur2.next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur2.next = pre2 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pre2 = cur2 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur2 = next2 &nbsp; &nbsp; &nbsp; &nbsp;head2 = pre2 &nbsp; &nbsp; &nbsp; &nbsp;dumpyNode3 = ListNode(-1) &nbsp; &nbsp; &nbsp; &nbsp;pHead = dumpyNode3 &nbsp; &nbsp; &nbsp; &nbsp;incre = 0 &nbsp; &nbsp; &nbsp; &nbsp;while head1 and head2: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val = head1.val+head2.val+incre &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;incre = val/10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val = val%10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head = ListNode(val) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead.next = head &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead = pHead.next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head1 = head1.next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head2 = head2.next &nbsp; &nbsp; &nbsp; &nbsp;while head1: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val = head1.val+incre &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;incre = val/10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val = val%10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head = ListNode(val) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead.next = head &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead = pHead.next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head1 = head1.next &nbsp; &nbsp; &nbsp; &nbsp;while head2: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val = head2.val+incre &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;incre = val/10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;val = val%10 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head = ListNode(val) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead.next = head &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead = pHead.next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head2 = head2.next &nbsp; &nbsp; &nbsp; &nbsp;if incre&gt;0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;head = ListNode(incre) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead.next = head &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pHead = pHead.next &nbsp; &nbsp; &nbsp; &nbsp;pHead = dumpyNode3.next &nbsp; &nbsp; &nbsp; &nbsp;cur1 = pHead &nbsp; &nbsp; &nbsp; &nbsp;pre = None &nbsp; &nbsp; &nbsp; &nbsp;while cur1: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;next1 = cur1.next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur1.next = pre &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pre = cur1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur1 = next1 &nbsp; &nbsp; &nbsp; &nbsp;return pre</td> 
 </tr> 
 </tbody> 
</table>

**3** **结语**

针对数组排序问题，提出的解决方法，证明该方法是有效的。其实上面的题目的思路都很简单，相当于把简单的排序从数组迁移到了链表中。个人认为技巧在于链表节点的生成与穿针引线，一般可以使用两个辅助节点，定义虚拟节点和游走节点，虚拟节点负责返回整个链表，游走节点负责穿针引线。以提高算法效率。