数据结构与算法 | Leetcode 206:Reverse Linked List

前面我们实现了几种常见的 链表 ，接下来，我们来聊聊如何实现 单链表 的反转？链表反转Leetcode 206: Reverse Linked List示例：Input: 1->2->3->4->5->NULLOutput: 5->4->3->2->1->NULLInput: NULLOutput: NULL我们可以通过循环遍历和递归这两种方式来实现链表的反转。遍历思路定义三个指针，分别为prev、curr、next，然后遍历所有node结点，并移动这三个指针，改变curr结点的next指向，指向prev结点，实现linkedList的反转。代码实现/** * 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 prev = null; ListNode curr = head; ListNode next = null; while(curr != null){ next = curr.next; curr.next = prev; prev = curr; curr = next; } head = prev; return head; }}源码递归其实递归的实现方式和前面循环的方式非常相似，前者是通过循环来移动指针，后者是通过递归来移动指针。定义一个递归接口，传入curr与prev节点作为参数，内部再将curr的作为下次递归调用的prev入参，curr.next 作为下次递归调用的curr入参。代码实现/* * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode reverseList(ListNode head){ return reverseRecursively(head, null); } public ListNode reverseRecursively(ListNode curr, ListNode prev) { if(curr == null){ return null; } if(curr.next == null){ ListNode head = curr; curr.next = prev; return head; } ListNode next1 = curr.next; curr.next = prev; ListNode head = reverseRecursively(next1, curr); return head; }}源码这两种方式的时间复杂度均为O(n)，空间复杂度均为O(1)。参考资料《数据结构与算法之美》