24. 反转链表

题目

官方地址

代码（双指针）

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode cur=head;ListNode pre=null;ListNode tmp=null;while(cur!=null){tmp=cur.next;cur.next=pre;pre=cur;cur=tmp;}return pre;}}

题解

1. 首先，我们定义了三个指针：cur，pre和tmp，它们都是指向链表节点的引用。
2. 我们将cur指针初始化为链表的头节点head，pre和tmp都初始化为null。
3. 然后，我们使用一个循环来遍历链表。循环的条件是当cur指针不为null时继续执行。
4. 在循环的每一次迭代中，我们首先将tmp指针指向cur节点的下一个节点。这是因为在改变cur.next指针之后，我们需要保留对原始下一个节点的引用，以便在下一次迭代中使用。
5. 接下来，我们将cur.next指针指向pre节点。这一步是实现节点翻转的关键。通过将当前节点的next指针指向前一个节点，我们将链表方向逆转。
6. 然后，我们将pre指针更新为cur节点，将cur指针更新为tmp节点。这样做是为了继续遍历链表，将指针向前移动一位。
7. 循环继续执行，直到cur指针为null，表示已经遍历完整个链表。
8. 最后，返回pre指针作为翻转后的链表的头节点。由于在循环结束时，pre指针指向原链表的最后一个节点，因此它现在是翻转后链表的头节点。

通过使用双指针方法，我们可以在不使用递归的情况下，通过修改指针的指向来实现链表的翻转。这种方法具有迭代的特点，适用于处理大型链表和节省内存的情况。

递归法

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode result=reverse(null,head);return result;}private ListNode reverse(ListNode pre,ListNode cur){if(cur==null){return pre;}ListNode tmp=cur.next;cur.next=pre;return reverse(cur,tmp);}}

题解

1. 首先，我们有一个公共方法reverseList，它接受一个链表的头节点head作为参数，并返回翻转后的链表的头节点。
2. 在reverseList方法内部，我们调用了另一个私有方法reverse，它接受两个参数：pre表示当前节点的前一个节点，cur表示当前节点。
3. 在reverse方法内部，首先进行终止条件的判断。如果当前节点cur为空，说明已经遍历到链表的尾部，这时候返回pre作为翻转后的链表的头节点。
4. 如果当前节点cur不为空，我们需要进行链表节点的翻转操作。
5. 首先，我们创建一个临时节点tmp，用于保存当前节点cur的下一个节点。
6. 然后，将当前节点cur的next指针指向前一个节点pre，实现翻转操作。
7. 接下来，我们通过递归调用reverse方法，将当前节点cur作为新的前一个节点pre，将临时节点tmp作为新的当前节点cur。
8. 递归调用会一直进行，直到遍历到链表的尾部。在递归的过程中，每次都将当前节点的next指针指向前一个节点，实现了链表节点的翻转。
9. 最后，当递归调用结束后，返回pre作为翻转后的链表的头节点。
   

利用栈

public ListNode reverseList(ListNode head) {// 如果链表为空，则返回空if (head == null) return null;// 如果链表中只有只有一个元素，则直接返回if (head.next == null) return head;// 创建栈 每一个结点都入栈Stack<ListNode> stack = new Stack<>();ListNode cur = head;while (cur != null) {stack.push(cur);cur = cur.next;}// 创建一个虚拟头结点ListNode pHead = new ListNode(0);cur = pHead;while (!stack.isEmpty()) {ListNode node = stack.pop();cur.next = node;cur = cur.next;}// 最后一个元素的next要赋值为空cur.next = null;return pHead.next;
}

1. 首先将所有的结点入栈
2. 然后创建一个虚拟虚拟头结点，让cur指向虚拟头结点。然后开始循环出栈，每出来一个元素，就把它加入到以虚拟头结点为头结点的链表当中，最后返回即可。