一、题目描述
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { } }
二、思路讲解
定义两个新的指针，分别指向当前元素和前一个元素，反向遍历链表，建立新的连接关系。
三、算法描述
1、迭代
假设链表为 1→2→3→∅，我们想要把它改成∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
2、递归
用递归的方式将节点一一连在新链表的头部，则实现了反转。
四、Java代码实现
1、迭代
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; } }
2、递归
/** * 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) { return doReverse(head, null); } public ListNode doReverse(ListNode node, ListNode list){ if(node == null){ return list; } //先保存下一个节点 ListNode temp = node.next; //将当前节点接到新建链表的头 node.next = list; return doReverse(temp, node); } }
五、时空复杂度分析
- 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
- 空间复杂度：O(1)。
六、其他代码实现
在力扣上偷的其他语言的代码，以供参考。
1、C++
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } };
2、C
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev = NULL; struct ListNode* curr = head; while (curr) { struct ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }
