Java双向链表反转方法卡顿及镜像异常问题求助

问题分析 #

1. while循环卡顿问题 #

原insertNode方法分支逻辑存在缺陷：当链表为空（head == null）时初始化head和tail后，未终止方法执行，导致后续pos == 0分支被重复触发。首次插入节点时，新节点的next和prev均指向自身，形成循环链表。后续调用length()方法时，会因循环链表无限遍历而卡住，导致reverse方法的while循环仅执行一次就无法继续。

2. 反转结果镜像异常问题 #

循环链表导致length()方法返回错误值，insertNode中pos > length()的判断会阻止后续节点插入；同时pos == 0插入时未正确维护链表结构，最终使得原链表[1,2,3,4,5]反转后出现[1,2,3,2,1]的镜像错误。

修复方案 #

修复insertNode方法 #

public void insertNode(int data, int pos) {
    Node newNode = new Node(data);
    if (head == null) {
        head = tail = newNode;
        return; // 初始化后直接返回，避免后续逻辑重复执行
    }
    int listLength = length();
    if (pos > listLength) {
        return;
    }
    if (pos == 0) {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
        // 头部插入时无需修改tail，保留原尾节点
    } else {
        Node temp = head;
        for (int i = 0; i < pos - 1 && temp.next != null; i++) {
            temp = temp.next;
        }
        if (temp.next == null) { // 插入到尾部
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        } else { // 插入到中间
            newNode.prev = temp;
            newNode.next = temp.next;
            temp.next.prev = newNode;
            temp.next = newNode;
        }
    }
}

简化并修复reverse方法 #

public static DoubleLinkedList reverse(DoubleLinkedList DL) {
    DoubleLinkedList result = new DoubleLinkedList();
    Node tempDL = DL.head;
    while (tempDL != null) {
        result.insertNode(tempDL.data, 0);
        tempDL = tempDL.next;
    }
    return result;
}

确保length()方法正确 #

public int length() {
    int count = 0;
    Node temp = head;
    while (temp != null) {
        count++;
        temp = temp.next;
    }
    return count;
}

修复说明 #

1. 在insertNode的空链表初始化块中添加return，避免重复执行插入逻辑，防止循环链表生成。
2. 提前计算链表长度，避免多次调用length()方法，同时防止链表结构变化导致的长度计算错误。
3. 移除reverse方法中冗余的空链表/单节点判断，循环逻辑可自然处理这些边界情况。

内容的提问来源于stack exchange，提问作者Karim G.