力扣面试题——分割链表

Question

我的想法是用两条链表来存储，再合并，如下是我的方法实现：

public ListNode partition(ListNode head, int x) {

    ListNode small=new ListNode(0);

    ListNode big=new ListNode(0);

    ListNode cur=head;

    ListNode l1=small;

    ListNode l2=big;

    while(cur!=null){

        if(cur.val<x){

            l1.next = cur;

        cur = cur.next;

        l1 = l1.next;

        l1.next = null;

        }else{

           l2 .next = cur;

        cur = cur.next;

        l2 = l2.next;

        l2.next = null;

        }

    }

    l1.next=big.next;

    return small.next;

}

请问为什么会报超出内存限制，我觉得代码没问题呀！求哪位大神帮帮忙看看，谢谢！

Answer 1

我认为是链表循环了吧，将节点添加到l1或l2链表的时候，没正确地更新cur节点的next指针。把那个节点添加到l1或l2链表之前，先将cur节点的next指针设置为null，断开循环，完后下面是尝试修改的代码

ListNode small = new ListNode(0);
ListNode big = new ListNode(0);
ListNode cur = head;
ListNode l1 = small;
ListNode l2 = big;

while (cur != null) {
    if (cur.val < x) {
        l1.next = cur;
        cur = cur.next;
        l1 = l1.next;
        l1.next = null;
    } else {
        l2.next = cur;
        cur = cur.next;
        l2 = l2.next;
        l2.next = null;
    }
}

l1.next = big.next;
return small.next;

望采纳