一文让你在也不怕面试官提问如何“反转单向链表”

什么是反转单向链表

其实所谓的反转单向链表，就是将一个原本顺序是“A->B->C->D”的单向链表变成“D->C->B->A”。这种操作就是反转单向链表。

实现思路

总体思路就是创建一个新的链表，每次从待反转的单向链表上摘下来一个节点，放到新链表的头节点后面。

代码实现

/**

* 反转单链表

*

* @param head 链表的头节点

*/

public void reversetSingleLinkedList(Node head) {

// 判断该链表是否为空，或者只有一个节点

if(head.next == null || head.next.next == null){

return;

}

// 定义辅助变量，遍历链表使用。

Node cur = head.next;

// 用于保存辅助节点（cur）的下一个节点。

Node next = null;

// 创建头节点（为反转链表使用）

Node reverseHead = new Node("reverseHead");

// 遍历待反转的链表

while (cur != null){

// 保存辅助节点（cur）的下一个节点

next = cur.next;

// 将辅助节点的指针域（指向下一个节点）指向reverseHead的下一个节点。

cur.next = reverseHead.next;

// 将reverseHead的指针域（指向下一个节点）指向cur

reverseHead.next = cur;

// 将辅助变量后移

cur = next;

}

// 将待反转链表头节点中指向下一个节点的指针域，指向反转链表头节点的下一个节点

head.next = reverseHead.next;

}

代码讲解

第一步：

cur.next = reverseHead.next;

reverseHead.next = cur;

第一行代码含义是，当每次循环时将用于遍历的辅助变量（cur）的指针域，指向新创建的反转链表头节点（reverseHead）的下一个节点。从而实现从待反转的链表上获取一个节点，并将这个节点放到反转链表头节点（reverseHead）的下一个节点前面。结合第二行代码（reverseHead.next = cur），就会实现每次从待反转的链表上获取一个节点，然后放到反转链表的头节点（reverseHead）后面。

第二步：

head.next = reverseHead.next;

当循环结束后reverseHead的结构就是反转后的链表。替换reverseHead头节点，将待反转链表中头节点的指针域，指向reverseHead.next（反转链表中头节点的下一个节点），从而实现单链表的反转。

结语

通过上面的方式可以轻松实现单链表的反转，是不是再也不怕面试官提问了？如果有哪些地方不是特别明白或者文章写的有问题，大家可以在评论区提出来。

今天的分享就先到这里了，看都看完了，点个赞再走吧！