Dart单链表mergeSort方法异常求助：调用触发索引越界错误

问题描述 #

基于Dart实现的单链表基础功能正常，但调用mergeSort时触发未处理的RangeError（索引越界），错误指向LinkedList的nodeAtIndex方法。单独测试split和merge方法功能正常，但递归执行归并排序时出错。

代码与报错信息 #

单链表实现代码 #

class Node {
  var data;
  Node? nextNode;

  Node(this.data, [this.nextNode]);

  @override
  String toString() {
    return '<Node data: $data>';
  }
}

class LinkedList {
  Node? head;
  var _count = 0;

  LinkedList();

  bool isEmpty() {
    return head == null;
  }

  int size() {
    Node? current = head;
    int count = 0;

    while (current != null) {
      count++;
      current = current.nextNode;
    }

    return count;
  }

  int get length {
    return _count;
  }

  void add(dynamic data) {
    var newNode = Node(data);
    newNode.nextNode = head;
    head = newNode;
    _count++;
  }

  void insert(dynamic data, int index) {
    if (index > _count) {
      throw IndexError.withLength(index, _count, message: 'index out of range');
    }

    if (index == 0) {
      add(data);
      return;
    }
    if (index > 0) {
      var newNode = Node(data);
      var position = index;
      var current = head;

      while (position > 1) {
        current = current?.nextNode!;
        position--;
      }

      var prevNode = current;
      var nextNode = current?.nextNode;

      prevNode?.nextNode = newNode;
      newNode.nextNode = nextNode;
    }

    _count++;
  }

  Node? nodeAtIndex(int index) {
    if (index >= _count) {
      throw IndexError.withLength(index, _count, message: 'index out of range');
    }

    if (index == 0) {
      return head;
    }

    Node? current = head;
    int position = 0;

    while (position < index) {
      current = current?.nextNode;
      position++;
    }

    return current;
  }

  Node? remove(dynamic key) {
    Node? current = head;
    Node? previous;
    bool found = false;

    while (current != null && !found) {
      if (current.data == key && current == head) {
        found = true;
        head = current.nextNode;
        _count--;
        return current;
      } else if (current.data == key) {
        found = true;
        previous?.nextNode = current.nextNode;
        _count--;
        return current;
      } else {
        previous = current;
        current = current.nextNode;
      }
    }

    return current;
  }

  Node? removeAtIndex(int index) {
    if (index >= _count) {
      throw IndexError.withLength(index, _count, message: 'index out of range');
    }

    Node? current = head;

    if (index == 0) {
      head = current?.nextNode;
      _count--;
      return current;
    }

    int position = index;

    while (position > 1) {
      current = current?.nextNode;
      position--;
    }

    Node? prevNode = current;
    current = current?.nextNode;
    Node? nextNode = current?.nextNode;

    prevNode?.nextNode = nextNode;
    _count--;

    return current;
  }

  Node? search(dynamic key) {
    var current = head;

    while (current != null) {
      if (current.data == key) {
        return current;
      } else {
        current = current.nextNode;
      }
    }

    return null;
  }

  @override
  String toString() {
    List<String> nodes = [];
    var current = head;

    while (current != null) {
      if (identical(current, head)) {
        nodes.add("[Head: ${current.data}]");
      } else if (current.nextNode == null) {
        nodes.add("[Tail: ${current.data}]");
      } else {
        nodes.add("[${current.data}]");
      }
      current = current.nextNode;
    }
    return nodes.join(' -> ');
  }
}

归并排序实现代码 #

import 'linked_list.dart';

LinkedList mergeSort(LinkedList linkedList) {
  if (linkedList.size() == 1) {
    return linkedList;
  } else if (linkedList.head == null) {
    return linkedList;
  }

  var (leftHalf, rightHalf) = split(linkedList);
  var left = mergeSort(leftHalf);
  var right = mergeSort(rightHalf);

  return merge(left, right);
}

(LinkedList, LinkedList) split(LinkedList linkedList) {
  if (linkedList.head == null) {
    LinkedList leftHalf = linkedList;
    LinkedList rightHalf = LinkedList();

    return (leftHalf, rightHalf);
  } else {
    var size = linkedList.size();
    var mid = size ~/ 2;
    var midNode = linkedList.nodeAtIndex(mid - 1);

    var leftHalf = linkedList;
    var rightHalf = LinkedList();
    rightHalf.head = midNode?.nextNode;
    midNode?.nextNode = null;

    return (leftHalf, rightHalf);
  }
}

LinkedList merge(LinkedList left, LinkedList right) {
  var merged = LinkedList();
  merged.add(0);
  var current = merged.head;

  var leftHead = left.head;
  var rightHead = right.head;

  while (leftHead != null || rightHead != null) {
    if (leftHead == null) {
      current?.nextNode = rightHead;
      rightHead = rightHead?.nextNode;
    } else if (rightHead == null) {
      current?.nextNode = leftHead;
      leftHead = leftHead.nextNode;
    } else {
      var leftData = leftHead.data;
      var rightData = rightHead.data;

      if (leftData < rightData) {
        current?.nextNode = leftHead;
        leftHead = leftHead.nextNode;
      } else {
        current?.nextNode = rightHead;
        rightHead = rightHead?.nextNode;
      }
    }
    current = current?.nextNode;
  }

  var head = merged.head?.nextNode;
  merged.head = head;

  return merged;
}

void main(List<String> args) {
  var l = LinkedList();

  l.add(99);
  l.add(25);
  l.add(3);
  l.add(47);

  print('Unsorted list: $l');

  final sortedList = mergeSort(l);
  print('Sorted list: $sortedList');
}

报错输出 #

Unsorted list: [Head: 47] -> [3] -> [25] -> [Tail: 99]

Unhandled exception:
RangeError: index out of range: no indices are valid: 0
#0      LinkedList.nodeAtIndex (file:///D:/Documents/Development/projects/dartpad/bin/linked_list.dart:116:7)
#1      split (file:///D:/Documents/Development/projects/dartpad/bin/merge_sort_linked_list.dart:27:30)
#2      mergeSort (file:///D:/Documents/Development/projects/dartpad/bin/merge_sort_linked_list.dart:10:31)
#3      mergeSort (file:///D:/Documents/Development/projects/dartpad/bin/merge_sort_linked_list.dart:12:15)
#4      main (file:///D:/Documents/Development/projects/dartpad/bin/merge_sort_linked_list.dart:84:22)
#5      _delayEntrypointInvocation.<anonymous closure> (dart:isolate-patch/isolate_patch.dart:294:33)
#6      _RawReceivePort._handleMessage (dart:isolate-patch/isolate_patch.dart:189:12)

Exited (255).

问题根源 #

split方法分割链表时，仅截断了节点引用，但未更新leftHalf和rightHalf的_count属性：

• 原链表的_count是总节点数，分割后leftHalf的_count仍保持原值，而非实际节点数mid
• rightHalf的_count初始为0，但实际节点数是size - mid
• 递归处理rightHalf时，mergeSort通过size()判断其长度为1，但nodeAtIndex方法用_count（0）校验索引，调用nodeAtIndex(0)时触发index >= _count的错误

修复方案 #

修改split方法，在分割链表后更新两个子链表的_count值：

(LinkedList, LinkedList) split(LinkedList linkedList) {
  if (linkedList.head == null) {
    LinkedList leftHalf = linkedList;
    LinkedList rightHalf = LinkedList();

    return (leftHalf, rightHalf);
  } else {
    var size = linkedList.size();
    var mid = size ~/ 2;
    var midNode = linkedList.nodeAtIndex(mid - 1);

    var leftHalf = linkedList;
    // 更新leftHalf的节点计数
    leftHalf._count = mid;
    
    var rightHalf = LinkedList();
    rightHalf.head = midNode?.nextNode;
    // 更新rightHalf的节点计数
    rightHalf._count = size - mid;
    
    midNode?.nextNode = null;

    return (leftHalf, rightHalf);
  }
}

验证 #

修复后运行main方法，输出正常：

Unsorted list: [Head: 47] -> [3] -> [25] -> [Tail: 99]
Sorted list: [Head: 3] -> [25] -> [47] -> [Tail: 99]

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