题目输入一个链表反转链表后输出新链表的表头。Reverse a singly linked list.Example:Input: 1-2-3-4-5-NULL Output: 5-4-3-2-1-NULLFollow up:A linked list can be reversed either iteratively or recursively. Could you implement both?2026.10.29又时隔四年了连反转链表都不会了……看了思路才写出来但还是比较straightforward的就是需要用prev, curr两个指针一个个小心遍历 老实连接链表就行没啥坑。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev; } }递归依旧不会只能死记硬背理解了。返回条件倒是写的出来然后如果不返回的话那就把当前head后面的部分反转好再回来处理head于是head后面的部分反转好的newHead就是reverseList(head.next)。这个newHead一直都是链表的最后一个节点不变只是它后面一直需要接上新的元素which is递归那层的head所以就是把head接到它原来的next后面就是head.next.next head就把head后面这串链表的尾巴接好了。然后需要设置head.next null来防止链表形成环。G老师的总结很到位你可以把ListNode newHead reverseList(head.next);理解成一句话「我不负责反转后面的链表我相信递归调用会帮我把后面的链表反转好并把反转后的头节点告诉我。」记住这个原则修改链表指针时不仅要建立需要的新连接也要考虑旧连接是否需要断开。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { 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; } }2022.12.19给想复杂了……还用了dummyHead然后发现dummyHead一会儿成环了一会儿多了个0……才意识到根本不需要dummyHead……以及时隔两年还是不会写递归……2020.10.13 Java差点没给写出来吓得我以为我连反转链表都不会了。看了下自己新写的代码比以前的要简洁多了有进步。对比了一下solutions居然除了变量名temp它起的是tempNext以外完全一毛一样惊呆。Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.Memory Usage: 38.7 MB, less than 6.72% of Java online submissions for Reverse Linked List./** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode curr head; ListNode prev null; while (curr ! null) { ListNode temp curr.next; curr.next prev; prev curr; curr temp; } return prev; } }还是不会写递归唉。知道了思路也在head.next.nexthead那里卡住了。Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.Memory Usage: 39.1 MB, less than 6.72% of Java online submissions for Reverse Linked List./** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; } ListNode node reverseList(head.next); head.next.next head; head.next null; return node; } }这道题没有什么特殊的技巧就是普普通通地做就好了也是一道非常经典的题面试高频题。链表的题首先要考虑给出的头节点为空的情况直接返回NULL。反转链表这个要格外注意不要把链表给断了因此我们设置三个指针分别指向当前节点curr、前一节点prev和后一节点next。在while循环中遍历整个链表小心翼翼地将curr的next设为prev并把prev和curr向后挪动一个直到curr的next为空时达到了链表的尾部把最后的curr设为反转链表的头节点/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead) { return NULL; } ListNode* prev NULL; ListNode* curr pHead; ListNode* new_head NULL; while (curr) { ListNode* next curr-next; if (!next) { new_head curr; } curr-next prev; prev curr; curr next; } return new_head; } };另外一种递归方法我理解了好久才搞明白其实还是比较难想的。首先递归基是当参数中的pHead为空或者pHead-next为空时就返回pHead作为反转链表的头节点。接下来通过递归调用这个函数把递归返回的结果其实仔细看会发现每次返回的都是原链表的最后一个节点也就是新链表的头存起来然后把当前指向的节点的下一个节点的next设为它自己这就把指针反过来了再把当前节点的next设为空方便下一次设置next毕竟当前节点在下一次就是前面那句提到的“当前节点的下一节点了最后返回的就是之前存起来的新链表的头。画了个图代码如下/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead || !pHead-next) { return pHead; } ListNode* pReversedNode ReverseList(pHead-next); pHead-next-next pHead; pHead-next NULL; return pReversedNode; } }; 题目输入一个链表反转链表后输出新链表的表头。Reverse a singly linked list.Example:Input: 1-2-3-4-5-NULL Output: 5-4-3-2-1-NULLFollow up:A linked list can be reversed either iteratively or recursively. Could you implement both?2026.10.29又时隔四年了连反转链表都不会了……看了思路才写出来但还是比较straightforward的就是需要用prev, curr两个指针一个个小心遍历 老实连接链表就行没啥坑。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev; } }递归依旧不会只能死记硬背理解了。返回条件倒是写的出来然后如果不返回的话那就把当前head后面的部分反转好再回来处理head于是head后面的部分反转好的newHead就是reverseList(head.next)。这个newHead一直都是链表的最后一个节点不变只是它后面一直需要接上新的元素which is递归那层的head所以就是把head接到它原来的next后面就是head.next.next head就把head后面这串链表的尾巴接好了。然后需要设置head.next null来防止链表形成环。G老师的总结很到位你可以把ListNode newHead reverseList(head.next);理解成一句话「我不负责反转后面的链表我相信递归调用会帮我把后面的链表反转好并把反转后的头节点告诉我。」记住这个原则修改链表指针时不仅要建立需要的新连接也要考虑旧连接是否需要断开。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { 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; } }2022.12.19给想复杂了……还用了dummyHead然后发现dummyHead一会儿成环了一会儿多了个0……才意识到根本不需要dummyHead……以及时隔两年还是不会写递归……2020.10.13 Java差点没给写出来吓得我以为我连反转链表都不会了。看了下自己新写的代码比以前的要简洁多了有进步。对比了一下solutions居然除了变量名temp它起的是tempNext以外完全一毛一样惊呆。Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.Memory Usage: 38.7 MB, less than 6.72% of Java online submissions for Reverse Linked List./** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode curr head; ListNode prev null; while (curr ! null) { ListNode temp curr.next; curr.next prev; prev curr; curr temp; } return prev; } }还是不会写递归唉。知道了思路也在head.next.nexthead那里卡住了。Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.Memory Usage: 39.1 MB, less than 6.72% of Java online submissions for Reverse Linked List./** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; } ListNode node reverseList(head.next); head.next.next head; head.next null; return node; } }这道题没有什么特殊的技巧就是普普通通地做就好了也是一道非常经典的题面试高频题。链表的题首先要考虑给出的头节点为空的情况直接返回NULL。反转链表这个要格外注意不要把链表给断了因此我们设置三个指针分别指向当前节点curr、前一节点prev和后一节点next。在while循环中遍历整个链表小心翼翼地将curr的next设为prev并把prev和curr向后挪动一个直到curr的next为空时达到了链表的尾部把最后的curr设为反转链表的头节点/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead) { return NULL; } ListNode* prev NULL; ListNode* curr pHead; ListNode* new_head NULL; while (curr) { ListNode* next curr-next; if (!next) { new_head curr; } curr-next prev; prev curr; curr next; } return new_head; } };另外一种递归方法我理解了好久才搞明白其实还是比较难想的。首先递归基是当参数中的pHead为空或者pHead-next为空时就返回pHead作为反转链表的头节点。接下来通过递归调用这个函数把递归返回的结果其实仔细看会发现每次返回的都是原链表的最后一个节点也就是新链表的头存起来然后把当前指向的节点的下一个节点的next设为它自己这就把指针反过来了再把当前节点的next设为空方便下一次设置next毕竟当前节点在下一次就是前面那句提到的“当前节点的下一节点了最后返回的就是之前存起来的新链表的头。画了个图代码如下/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead || !pHead-next) { return pHead; } ListNode* pReversedNode ReverseList(pHead-next); pHead-next-next pHead; pHead-next NULL; return pReversedNode; } };