如何实现链表中点分割（奇数长度前半含额外节点）及代码修复

需求 #

实现链表分割功能，要求链表长度为奇数时，前半部分包含额外节点。需通过以下测试用例：

>>> s1, s2 = x.split()
>>> s1
Head:Node(-7.5)
Tail:Node(3.75)
List:-7.5 -> 0 -> 1 -> 3 -> 3.75
>>> s2
Head:Node(4)
Tail:Node(9.78)
List:4 -> 5 -> 8.76 -> 9.78

已有链表类代码 #

以下是不可修改的类构造方法及基础方法：

def __init__(self):   # 不允许修改构造方法
    self.head=None
    self.tail=None

def __str__(self):   # 不允许修改此方法
    temp=self.head
    out=[]
    while temp:
        out.append(str(temp.value))
        temp=temp.next
    out=' -> '.join(out) 
    return f'Head:{self.head}\nTail:{self.tail}\nList:{out}'

__repr__=__str__


def isEmpty(self):
    return self.head == None

def __len__(self):
    count=0
    current=self.head
    while current:
        current=current.next
        count+=1
    return count

我的尝试实现 #

我编写了以下split方法，但无法通过测试，且不能使用break/continue、节点数据交换、将链表数据复制到其他结构（如Python列表）或内置复制方法：

def split(self):
    # find the half length of the list
    mid = round(len(self) // 2)
    # create two lists - to store both halves
    left = SortedLinkedList()
    right = SortedLinkedList()
    # take reference to head
    current = self.head
    # loop for mid number of times
    for i in range(mid):
        # add value of current node to left list
        left.add(current.value)
        # advance current
        current = current.next
    # now loop as long as current is not None
    while current:
        # add value of current node to right list
        right.add(current.value)
        # advance current
        current = current.next
    # return both lists
    return left, right

测试失败结果 #

File "c:\python\CMPSC 132 sp\LAB4.py", line 44, in __main__.SortedLinkedList
Failed example:
    s1
Expected:
    Head:Node(-7.5)
    Tail:Node(3.75)
    List:-7.5 -> 0 -> 1 -> 3 -> 3.75
Got:
    Head:Node(-7.5)
    Tail:Node(3)
    List:-7.5 -> 0 -> 1 -> 3
Trying:
    s2
Expecting:
    Head:Node(4)
    Tail:Node(9.78)
    List:4 -> 5 -> 8.76 -> 9.78
**********************************************************************
File "c:\python\CMPSC 132 sp\LAB4.py", line 48, in __main__.SortedLinkedList
Failed example:
    s2
Expected:
    Head:Node(4)
    Tail:Node(9.78)
    List:4 -> 5 -> 8.76 -> 9.78
Got:
    Head:Node(3.75)
    Tail:Node(9.78)
    List:3.75 -> 4 -> 5 -> 8.76 -> 9.78

修复方案 #

你的代码存在两个核心问题：

1. 中间节点数计算错误：round(len(self)//2)无法满足奇数长度时前半部分多一个节点的要求，正确的计算方式应为(len(self) + 1) // 2。比如总长度为9时，(9+1)//2=5，刚好让前半部分包含5个节点。
2. 错误使用SortedLinkedList的add方法：add方法会按排序规则插入元素，而非保持原链表的顺序，导致3.75被错误插入到s2的头部。正确的做法是直接拆分原链表的节点，手动设置新链表的head和tail，避免复制值引发的排序问题。

修改后的split方法如下：

def split(self):
    total_len = len(self)
    mid = (total_len + 1) // 2  # 确保奇数长度时前半部分多一个节点
    left = SortedLinkedList()
    right = SortedLinkedList()
    
    if total_len == 0:
        return left, right
    
    # 拆分原链表到left
    left.head = self.head
    current = self.head
    # 移动到left的最后一个节点
    for _ in range(mid - 1):
        current = current.next
    left.tail = current
    
    # 拆分剩余节点到right
    right.head = current.next
    if right.head is not None:
        # 找到right的尾节点
        right_current = right.head
        while right_current.next is not None:
            right_current = right_current.next
        right.tail = right_current
    else:
        right.tail = None
    
    # 切断左右链表的连接
    current.next = None
    # 重置原链表的头尾（可选，根据需求决定是否保留原链表数据）
    self.head = None
    self.tail = None
    
    return left, right

这个方案直接操作链表节点的引用，既保持了原链表的顺序，又正确划分了前后两部分的节点数量，完全符合测试用例要求。

内容的提问来源于stack exchange，提问作者Toodles