内容简介:前面我们实现了几种常见的链表 ,接下来,我们来聊聊如何实现示例:
前面我们实现了几种常见的链表 ,接下来,我们来聊聊如何实现 单链表 的反转。
链表反转
Leetcode 206: Reverse Linked List
示例:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Input: NULL Output: 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)。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 算法与数据结构之递归算法
- Python 数据结构与算法 —— 初识算法
- js实现数据结构及算法之排序算法
- 数据结构和算法面试题系列—递归算法总结
- 数据结构和算法面试题系列—随机算法总结
- 数据结构与算法——常用排序算法及其Java实现
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。