单链表双节点交换Java实现的空前驱分支逻辑疑问
你会有这个疑惑,本质是把单链表交换里两类独立的指针修改当成了重复操作。单链表想完成两个节点的交换,需要调整的连接关系拆成完全独立的两部分,缺了哪一部分都会直接断链:
- 代码最后三行的next指针交换,只调整两个待交换节点自己的后继指向:也就是X原来后面接谁、Y原来后面接谁,换个位置接。
- 分支里的prev指向调整,调整的是两个待交换节点的前驱节点的后续指向:也就是原来排在X前面的节点、原来排在Y前面的节点,现在要分别接谁。
就拿最普通的非头节点交换场景举例,链表原本的结构是 A → X → B → Y → C,待交换的节点是X和Y。
如果只跑最后三行的next交换:
- 先暂存Y的后继:
temp = Y.next = C - 把Y的后继改成X原来的后继:
Y.next = X.next = B - 把X的后继改成Y原来的后继:
X.next = temp = C
改完两个节点自己的指向之后,原来的前驱链路根本没动:A还是指着X,B还是指着Y。最后拼出来的链路是断的:A → X → C 、 B → Y → B,不仅断成两截,还在B和Y的位置绕了个环,根本没完成交换。
这时候分支里的操作才是补全连接的关键:
- 把X的前驱A的后继改成Y:
A.next = Y - 把Y的前驱B的后继改成X:
B.next = X
把这两步和之前的next交换拼起来,才是正确的交换结果:A → Y → B → X → C
prevDataX == null / prevDataY == null 的判断,就是用来识别“待交换节点本身就是链表头”的情况——链表头没有前驱节点,根本不存在可以修改的prev指针,要是硬写prev.next = 其他节点直接就触发空指针异常。
这种场景下你没法通过改前驱的next来把新的头接到链路上,就只能直接修改整个链表的头指针,把换完位置后的新头记下来,不然整个链表的访问入口就丢了。
比如链表结构是 X → B → Y → C,待交换的X本身就是头,prevX是null。如果只靠最后三行的next交换,头指针还是死死指着X,整个链路的排头根本没换,交换等于白做。这时候就需要特殊分支把新的头赋值给head变量,保证链表入口正确。
顺便提一句,你找的这段公开参考实现其实藏了个相邻节点的边界bug:如果两个待交换节点紧挨着(X的next直接就是Y),现在的分支执行顺序会把指针绕成环,这也是单链表交换题面试里最常被深挖的细节。
内容的提问来源于stack exchange,提问作者rickygrimes

