leetcode 题号#206 反转链表

本文主要是介绍leetcode 题号#206 反转链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

查看题目详情可点击此处。

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路

反转单链表应该算是链表中比较常见的操作，使用了循环和递归两种方式来解决。

• 循环
  首先讲一下循环的思路。其实有两条链表，一条是需要进行反转的链表（以下称为(链表s），一条是已经被反转的链表（以下称为链表r），刚开始时链表r是个空链表，对链表s进行遍历，当遍历到一个结点时，将链表s的头结点向后移动一个结点，于是链表s的头结点就会被空出来，被空出的头结点就可以作为链表r的头结点插入链表r，重复操作，直至链表s遍历到尾结点，代码如下。

class Solution {public ListNode reverseList(ListNode head) {ListNode reverseHead = null, posHead = null;ListNode curr = head;while(curr != null) {posHead = curr.next;curr.next = reverseHead;reverseHead = curr;curr = posHead;}return reverseHead;}
}

• 递归
  递归的关键是先找到递归公式，我们可以把整条链的反转分解为链上每个结点的反转，而结点的反转其实是由指向后一个结点转化为被后一个结点指向，转变为公式就是

$reverse(node)=reverse(nextNode)+nextNodePoint(node)$
reverse表示反转函数
nextNode表示进行反转的结点的下一结点
nextNodePoint表示下一结点的后继指针指向进行反转的结点

有了递归公式之后就需要找到递归公式的常量值，也就是递归方法结束的条件。反转的结束结点就是链表的尾结点，当结点的后继指针为NULL时就可以结束递归

当结点的后继指针为空时
$reverse(node)=node$

递归的方式分析结束了，代码如下。

class Solution {public ListNode reverseList(ListNode node) {if(node == null || node.next == null) {return node;}ListNode reverseHead = reverseList(node.next);node.next.next = node;node.next = null;return reverseHead;}
}

这篇关于leetcode 题号#206 反转链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---