难度: Medium
Submission
运行时间: 156 ms
内存: 45.4 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
pre, cur = head, head.next
while cur:
if cur.val < 0:
pre.next = cur.next
cur.next = head
head = cur
cur = pre.next
else:
pre = cur
cur = cur.next
return head
Explain
该题解通过链表的遍历，将所有的负数节点移动到链表的前部，达到整体排序的效果。算法从头节点开始遍历，利用两个指针pre和cur，其中pre是cur的前驱节点。在遍历过程中，如果发现当前节点cur的值为负数，则将该节点从链表中断开，并将其插入到链表的最前端，更新head指向新的头节点。然后继续遍历下一个节点。如果cur的值非负，只需移动pre和cur指针继续遍历即可。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head # 如果链表为空或只有一个节点，直接返回
pre, cur = head, head.next # 初始化前驱节点和当前节点
while cur:
if cur.val < 0: # 当前节点的值为负数
pre.next = cur.next # 将当前节点从链表中断开
cur.next = head # 将当前节点插入到链表的最前端
head = cur # 更新头节点
cur = pre.next # 移动当前节点到下一个节点
else:
pre = cur # 移动前驱节点
cur = cur.next # 移动当前节点
return head # 返回重新排序后的链表头节点
Explore
是的，这种算法中，如果连续存在多个负数节点，其顺序会被倒置。每次遇到负数节点cur，它都会被移动到链表的最前端。因此，较后出现的负数节点会先被移动到前端，导致原始的顺序反转。
在这种情况下，pre的正确性不会受影响。当cur为负数时，即便pre和cur紧邻，更新cur.next指向头节点之后再将pre.next设置为cur.next（此时cur已经移动）仍然可以保持链表的完整性。这是因为cur的移动是先断开与pre的连接，然后再重新连接到链表的前端。
当head节点为负数时，这种初始化不会影响算法的正确执行。因为即便head为负数，算法首次进入循环时不会对head节点进行任何操作；它只是设置了后续遍历的起点。head节点（如果是负数）已经在最前端，因此不需要移动。
这种操作考虑了所有边界情况。即使链表只有一个节点或所有节点都是负数，直接更新head为cur仍然是有效的。如果链表只有一个节点，该节点移动后仍然是head。如果所有节点都是负数，每个节点都将按遇到的顺序依次移到前端，最后一个负数节点将成为新的head。