| 代码随想录 | 您所在的位置：网站首页 › go反转链表思路 › 代码随想录 |
代码随想录
|
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！ 反转链表的写法很简单，一些同学甚至可以背下来但过一阵就忘了该咋写，主要是因为没有理解真正的反转过程。 # 206.反转链表力扣题目链接 (opens new window) 题意：反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL # 算法公开课《代码随想录》算法视频公开课 (opens new window)：帮你拿下反转链表 | LeetCode：206.反转链表 (opens new window)，相信结合视频再看本篇题解，更有助于大家对本题的理解。 # 思路如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。 其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:
之前链表的头节点是元素1， 反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向。 那么接下来看一看是如何反转的呢？ 我们拿有示例中的链表来举例，如动画所示：（纠正：动画应该是先移动pre，在移动cur）
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。 然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。 为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。 # 双指针法 class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* temp; // 保存cur的下一个节点 ListNode* cur = head; ListNode* pre = NULL; while(cur) { temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next cur->next = pre; // 翻转操作 // 更新pre 和 cur指针 pre = cur; cur = temp; } return pre; } }; 12345678910111213141516时间复杂度: O(n) 空间复杂度: O(1) # 递归法递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。 关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。 具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。 class Solution { public: ListNode* reverse(ListNode* pre,ListNode* cur){ if(cur == NULL) return pre; ListNode* temp = cur->next; cur->next = pre; // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步 // pre = cur; // cur = temp; return reverse(cur,temp); } ListNode* reverseList(ListNode* head) { // 和双指针法初始化是一样的逻辑 // ListNode* cur = head; // ListNode* pre = NULL; return reverse(NULL, head); } }; 12345678910111213141516171819时间复杂度: O(n), 要递归处理链表的每个节点 空间复杂度: O(n), 递归调用了 n 层栈空间我们可以发现，上面的递归写法和双指针法实质上都是从前往后翻转指针指向，其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向。 具体代码如下（带详细注释）： class Solution { public: ListNode* reverseList(ListNode* head) { // 边缘条件判断 if(head == NULL) return NULL; if (head->next == NULL) return head; // 递归调用，翻转第二个节点开始往后的链表 ListNode *last = reverseList(head->next); // 翻转头节点与第二个节点的指向 head->next->next = head; // 此时的 head 节点为尾节点，next 需要指向 NULL head->next = NULL; return last; } }; 12345678910111213141516时间复杂度: O(n) 空间复杂度: O(n) # 其他语言版本 # Java： // 双指针 class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; ListNode temp = null; while (cur != null) { temp = cur.next;// 保存下一个节点 cur.next = prev; prev = cur; cur = temp; } return prev; } } 123456789101112131415// 递归 class Solution { public ListNode reverseList(ListNode head) { return reverse(null, head); } private ListNode reverse(ListNode prev, ListNode cur) { if (cur == null) { return prev; } ListNode temp = null; temp = cur.next;// 先保存下一个节点 cur.next = prev;// 反转 // 更新prev、cur位置 // prev = cur; // cur = temp; return reverse(cur, temp); } } 12345678910111213141516171819// 从后向前递归 class Solution { ListNode reverseList(ListNode head) { // 边缘条件判断 if(head == null) return null; if (head.next == null) return head; // 递归调用，翻转第二个节点开始往后的链表 ListNode last = reverseList(head.next); // 翻转头节点与第二个节点的指向 head.next.next = head; // 此时的 head 节点为尾节点，next 需要指向 NULL head.next = null; return last; } } 12345678910111213141516# Python： （版本一）双指针法 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: cur = head pre = None while cur: temp = cur.next # 保存一下 cur的下一个节点，因为接下来要改变cur->next cur.next = pre #反转 #更新pre、cur指针 pre = cur cur = temp return pre 1234567891011121314151617（版本二）递归法 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: return self.reverse(head, None) def reverse(self, cur: ListNode, pre: ListNode) -> ListNode: if cur == None: return pre temp = cur.next cur.next = pre return self.reverse(temp, cur) 12345678910111213141516# Go： //双指针 func reverseList(head *ListNode) *ListNode { var pre *ListNode cur := head for cur != nil { next := cur.Next cur.Next = pre pre = cur cur = next } return pre } //递归 func reverseList(head *ListNode) *ListNode { return help(nil, head) } func help(pre, head *ListNode)*ListNode{ if head == nil { return pre } next := head.Next head.Next = pre return help(head, next) } 123456789101112131415161718192021222324252627# JavaScript: /** * @param {ListNode} head * @return {ListNode} */ // 双指针： var reverseList = function(head) { if(!head || !head.next) return head; let temp = null, pre = null, cur = head; while(cur) { temp = cur.next; cur.next = pre; pre = cur; cur = temp; } // temp = cur = null; return pre; }; // 递归： var reverse = function(pre, head) { if(!head) return pre; const temp = head.next; head.next = pre; pre = head return reverse(pre, temp); } var reverseList = function(head) { return reverse(null, head); }; // 递归2 var reverse = function(head) { if(!head || !head.next) return head; // 从后往前翻 const pre = reverse(head.next); head.next = pre.next; pre.next = head; return head; } var reverseList = function(head) { let cur = head; while(cur && cur.next) { cur = cur.next; } reverse(head); return cur; }; 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950# TypeScript: // 双指针法 function reverseList(head: ListNode | null): ListNode | null { let preNode: ListNode | null = null, curNode: ListNode | null = head, tempNode: ListNode | null; while (curNode) { tempNode = curNode.next; curNode.next = preNode; preNode = curNode; curNode = tempNode; } return preNode; }; // 递归（从前往后翻转） function reverseList(head: ListNode | null): ListNode | null { function recur(preNode: ListNode | null, curNode: ListNode | null): ListNode | null { if (curNode === null) return preNode; let tempNode: ListNode | null = curNode.next; curNode.next = preNode; preNode = curNode; curNode = tempNode; return recur(preNode, curNode); } return recur(null, head); }; // 递归（从后往前翻转） function reverseList(head: ListNode | null): ListNode | null { if (head === null) return null; let newHead: ListNode | null; function recur(node: ListNode | null, preNode: ListNode | null): void { if (node.next === null) { newHead = node; newHead.next = preNode; } else { recur(node.next, node); node.next = preNode; } } recur(head, null); return newHead; }; 12345678910111213141516171819202122232425262728293031323334353637383940414243# Ruby: # 双指针 # Definition for singly-linked list. # class ListNode # attr_accessor :val, :next # def initialize(val = 0, _next = nil) # @val = val # @next = _next # end # end def reverse_list(head) # return nil if head.nil? # 循环判断条件亦能起到相同作用因此不必单独判断 cur, per = head, nil until cur.nil? tem = cur.next cur.next = per per = cur cur = tem end per end # 递归 # Definition for singly-linked list. # class ListNode # attr_accessor :val, :next # def initialize(val = 0, _next = nil) # @val = val # @next = _next # end # end def reverse_list(head) reverse(nil, head) end def reverse(pre, cur) return pre if cur.nil? tem = cur.next cur.next = pre reverse(cur, tem) # 通过递归实现双指针法中的更新操作 end 12345678910111213141516171819202122232425262728293031323334353637383940# Kotlin: fun reverseList(head: ListNode?): ListNode? { var pre: ListNode? = null var cur = head while (cur != null) { val temp = cur.next cur.next = pre pre = cur cur = temp } return pre } 1234567891011/** * Example: * var li = ListNode(5) * var v = li.`val` * Definition for singly-linked list. * class ListNode(var `val`: Int) { * var next: ListNode? = null * } */ class Solution { fun reverseList(head: ListNode?): ListNode? { // temp用来存储临时的节点 var temp: ListNode? // cur用来遍历链表 var cur: ListNode? = head // pre用来作为链表反转的工具 // pre是比pre前一位的节点 var pre: ListNode? = null while (cur != null) { // 临时存储原本cur的下一个节点 temp = cur.next // 使cur下一节点地址为它之前的 cur.next = pre // 之后随着cur的遍历移动pre pre = cur; // 移动cur遍历链表各个节点 cur = temp; } // 由于开头使用pre为null,所以cur等于链表本身长度+1， // 此时pre在cur前一位，所以此时pre为头节点 return pre; } } 123456789101112131415161718192021222324252627282930313233# Swift： /// 双指针法 (迭代) /// - Parameter head: 头结点 /// - Returns: 翻转后的链表头结点 func reverseList(_ head: ListNode?) -> ListNode? { if head == nil || head?.next == nil { return head } var pre: ListNode? = nil var cur: ListNode? = head var temp: ListNode? = nil while cur != nil { temp = cur?.next cur?.next = pre pre = cur cur = temp } return pre } /// 递归 /// - Parameter head: 头结点 /// - Returns: 翻转后的链表头结点 func reverseList2(_ head: ListNode?) -> ListNode? { return reverse(pre: nil, cur: head) } func reverse(pre: ListNode?, cur: ListNode?) -> ListNode? { if cur == nil { return pre } let temp: ListNode? = cur?.next cur?.next = pre return reverse(pre: cur, cur: temp) } 123456789101112131415161718192021222324252627282930313233# C:双指针法： struct ListNode* reverseList(struct ListNode* head){ //保存cur的下一个结点 struct ListNode* temp; //pre指针指向前一个当前结点的前一个结点 struct ListNode* pre = NULL; //用head代替cur，也可以再定义一个cur结点指向head。 while(head) { //保存下一个结点的位置 temp = head->next; //翻转操作 head->next = pre; //更新结点 pre = head; head = temp; } return pre; } 1234567891011121314151617递归法： struct ListNode* reverse(struct ListNode* pre, struct ListNode* cur) { if(!cur) return pre; struct ListNode* temp = cur->next; cur->next = pre; //将cur作为pre传入下一层 //将temp作为cur传入下一层，改变其指针指向当前cur return reverse(cur, temp); } struct ListNode* reverseList(struct ListNode* head){ return reverse(NULL, head); } 12345678910111213# PHP: // 双指针法： function reverseList($head) { $cur = $head; $pre = NULL; while($cur){ $temp = $cur->next; $cur->next = $pre; $pre = $cur; $cur = $temp; } return $pre; } 123456789101112# Scala:双指针法： object Solution { def reverseList(head: ListNode): ListNode = { var pre: ListNode = null var cur = head while (cur != null) { var tmp = cur.next cur.next = pre pre = cur cur = tmp } pre } } 12345678910111213递归法： object Solution { def reverseList(head: ListNode): ListNode = { reverse(null, head) } def reverse(pre: ListNode, cur: ListNode): ListNode = { if (cur == null) { return pre // 如果当前cur为空，则返回pre } val tmp: ListNode = cur.next cur.next = pre reverse(cur, tmp) // 此时cur成为前一个节点，tmp是当前节点 } } 123456789101112131415# Rust:双指针法： impl Solution { pub fn reverse_list(head: Option) -> Option { let mut cur = head; let mut pre = None; while let Some(mut node) = cur.take() { cur = node.next; node.next = pre; pre = Some(node); } pre } } 123456789101112递归法： impl Solution { pub fn reverse_list(head: Option) -> Option { fn rev( mut head: Option, mut pre: Option, ) -> Option { if let Some(mut node) = head.take() { let cur = node.next; node.next = pre; pre = Some(node); return rev(cur, pre); } pre } rev(head, None) } } 1234567891011121314151617# C#:三指针法， 感觉会更直观： public LinkNumbers Reverse() { ///用三指针，写的过程中能够弥补二指针在翻转过程中的想象 LinkNumbers pre = null; var move = root; var next = root; while (next != null) { next = next.linknext; move.linknext = pre; pre = move; move = next; } root = pre; return root; } ///LinkNumbers的定义 public class LinkNumbers { /// /// 链表值 /// public int value { get; set; } /// /// 链表指针 /// public LinkNumbers linknext { get; set; } } 12345678910111213141516171819202122232425262728293031# 其他解法 # 使用虚拟头结点解决链表反转使用虚拟头结点，通过头插法实现链表的反转（不需要栈） // 迭代方法：增加虚头结点，使用头插法实现链表翻转 public static ListNode reverseList1(ListNode head) { // 创建虚头结点 ListNode dumpyHead = new ListNode(-1); dumpyHead.next = null; // 遍历所有节点 ListNode cur = head; while(cur != null){ ListNode temp = cur.next; // 头插法 cur.next = dumpyHead.next; dumpyHead.next = cur; cur = temp; } return dumpyHead.next; } 12345678910111213141516# 使用栈解决反转链表的问题 首先将所有的结点入栈 然后创建一个虚拟虚拟头结点，让cur指向虚拟头结点。然后开始循环出栈，每出来一个元素，就把它加入到以虚拟头结点为头结点的链表当中，最后返回即可。 public ListNode reverseList(ListNode head) { // 如果链表为空，则返回空 if (head == null) return null; // 如果链表中只有只有一个元素，则直接返回 if (head.next == null) return head; // 创建栈 每一个结点都入栈 Stack 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; } 123456789101112131415161718192021222324采用这种方法需要注意一点。就是当整个出栈循环结束以后，cur正好指向原来链表的第一个结点，而此时结点1中的next指向的是结点2，因此最后还需要cur.next = null
← 3. 设计链表 5. 两两交换链表中的节点 → @2021-2022 代码随想录 版权所有 粤ICP备19156078号 |
【本文地址】
公司简介
联系我们