链表是计算机科学中常用的数据结构之一，它由一系列节点构成，每个节点包含一个值和指向下一个节点的指针。链表的灵活性使其在许多场景下被广泛应用，但其中的一个常见问题是如何反转链表。我们来了解下面两种实现链表反转的方法。
使用虚拟头节点来辅助实现链表反转
首先我们先来建立一个虚拟节点dummyNode，并且使dummyNode.next=head,这样就可以很好的简化我们的操作。
public ListNode reverseList(ListNode head) { ListNode dummyNode = new ListNode(-1); ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = dummyNode.next; dummyNode.next = cur; cur = next; } return dummyNode.next; }
在循环体中，首先将cur.next赋值给next,用于保存cur的下一个节点。然后将dummyNode.next赋值给cur.next,即将cur与dummyNode相连，形成一个新的链表。接着将cur赋值给dummyNode.next,即将dummyNode与下一个节点相连。最后将next赋值给cur,继续遍历链表。
直接操作链表实现反转
public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; }
方法内部定义了两个变量pre和cur,分别表示当前节点的前一个节点和当前节点。初始时，pre为null,cur为head。
接下来是一个while循环，当cur不为null时，循环继续执行。在循环内部，首先将cur的下一个节点赋值给next,然后将cur的next指针指向pre,即将当前节点cur与前一个节点pre相连。接着将pre赋值给cur,表示当前节点变为前一个节点。最后将next赋值给cur,表示将当前节点更新为下一个节点。
循环结束后，pre即为反转后的链表头节点，返回pre即可。
使用递归来实现链表反转
public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }
- 首先判断链表是否为空或只有一个节点，如果是，则直接返回head,因为不需要反转。
- 如果链表有多个节点，递归调用reverseList(head.next),将链表的剩余部分反转，并将新的头节点赋值给newHead。
- 接下来，将原链表的尾节点与新链表的头部相连，即将head.next.next指向head。
- 将原链表的尾节点置为null,表示已经处理完毕。
- 最后返回新的头节点newHead。
指定区间反转
指定区间反转我们有两种方法：头插法与穿针引线法。
我们以力扣92题做测试
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
头插法
具体思路就是在需要反转的区间内，每遍历一个节点，就让这个新节点来到反转的起始位置
public ListNode reverseBetween(ListNode head, int left, int right) { if (head == null) { return head; } ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; for (int i = 0; i < left - 1; i++) { pre = pre.next; } ListNode cur = pre.next; ListNode next = null; for (int i = 0; i < right - left; i++) { next = cur.next; cur.next = next.next; next.next = pre.next; pre.next = next; } return dummyNode.next; }
- 首先，如果链表为空(即head为null),则直接返回空链表。
- 接下来，创建一个虚拟节点dummyNode,并将其next指针指向head。这样做的目的是为了方便处理边界情况，例如当left为1时，不需要对原始链表进行任何操作，直接返回dummyNode即可。
- 然后，使用一个for循环遍历链表，找到第left个节点的前一个节点pre。接着，将cur指针指向pre的下一个节点，即第left个节点。
- 接下来，使用另一个for循环遍历链表，从第left个节点开始，直到第right个节点。在每次循环中，首先将next指针指向cur的下一个节点，然后将cur的next指针指向next的下一个节点，将next的next指针指向pre的下一个节点，最后将pre的next指针指向next。这样就完成了链表中从第left个节点到第right个节点之间的节点反转操作。
- 最后，返回dummyNode的next指针，即反转后的链表的头节点。
穿针引线法
大体思路就是确定好需要反转的部分，用一个反正链表的方法把需要反转的部分反转然后接回去。
public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; for (int i = 0; i < left - 1; i++) { pre = pre.next; } ListNode rightNode = pre; for (int i = 0; i < right - left + 1; i++) { rightNode = rightNode.next; } ListNode leftNode = pre.next; ListNode succ = rightNode.next; rightNode.next = null; reverse(leftNode); pre.next = rightNode; leftNode.next = succ; return dummyNode.next; } public void reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; }
- 创建一个虚拟头节点dummyNode,并将其next指向head。
- 创建一个指针pre,初始化为dummyNode。
- 遍历链表，找到第left-1个节点的前一个节点，将其赋值给pre。
- 找到第left个节点的前一个节点，将其赋值给rightNode。
- 找到第right个节点的下一个节点，将其赋值给leftNode。
- 找到第right+1个节点，将其赋值给succ。
- 将rightNode的next指针设为null,表示反转后的链表不包含第right个节点。
- 调用reverse方法，反转leftNode到rightNode之间的所有节点。
- 将pre的next指针指向rightNode,表示反转后的链表包含第left个节点和第right个节点。
- 将leftNode的next指针指向succ,表示反转后的链表包含第left+1个节点和第right+1个节点。
- 返回dummyNode的next指针，即反转后的链表的头节点。
