206.反转链表

发表于 更新于 分类于 ，

题目

反转一个单链表。

示例:

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

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路

这道题可以使用迭代和递归两种形式来反转链表,先说迭代:

用迭代来反转单链表,也就相当于将每一个节点的头节点,放到自己的尾节点来,所以步骤应该是这样的:

  1. 将原链表头节点的尾部进行临时保存,防止断链丢失所有数据.
  2. 取出头节点,将null节点接入头节点,成为新链.
  3. 再将刚刚临时保存的链表头节点取出,将新链接入此头节点尾部,再次成为新链.
  4. 重复以上步骤直到临时保存的链表为null.

用递归来反转链表,就要按照递归的解题步骤,找到递归的几个要素:

  1. 首先要坚信我们的函数已经可以实现所需功能,哪怕它还没写完,但是我们要明确这个函数已经可以实现这个功能了,所以我们先写出这个已经实现功能的函数:

    1
    2
    3
    4
    public ListNode ReverseList(ListNode head)
    {
        
    }

  2. 找出递归结束的条件.这道题显然我们可以知道,当链表的长度为1时,不需要反转了,直接返回它本身就可以了:

    1
    2
    3
    4
    5
    6
    7
    public ListNode ReverseList(ListNode head)
    {
        if (head == null || head.next == null)
        {
            return head;
        }
    }

  3. 接下来我们要做的就是找出怎么将这个问题化为它的子问题,可以知道,假如现在的链表是这样的:

    1->2->3->4

    那假如我们将它的头节点后面进行反转,那后面那部分链表将会变成

    1->2<-3<-4

    1(head)还是头节点,它的下一个节点还是2(head.next),但是后面的部分已经反转完成了,所以现在要做的就是将2(head.next)的下一个节点变为1(head),而将1(head)的下一个节点变为null,所以这时候代码应该是这样的:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public ListNode ReverseList(ListNode head)
    {
        if (head == null || head.next == null)
        {
            return head;
        }
        ListNode newLinkedList = ReverseList(head.next);//接收已经反转了的链表.
        head.next.next = head;//将2(head.next)的下一个节点(next)变为1(head).
        head.next = null;//将1(head)的下一个节点变为null.
        return newLinkedList;
    }

代码

迭代版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode ReverseList(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }
    ListNode newLinkedList = null;//创建一个新的链表.
    while (head != null)
    {
        ListNode tempNode = head.next;//创建临时链表存放头节点的尾巴.
        head.next = newLinkedList;//将新链表接到头节点后面.
        newLinkedList = head;//再次成为新链表.
        head = tempNode;//将临时链表覆盖原链表.
    }
    return newLinkedList;
}

递归版本:

1
2
3
4
5
6
7
8
9
10
11
public ListNode ReverseList(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }
    ListNode newLinkedList = ReverseList(head.next);//接收已经反转了的链表.
    head.next.next = head;//将2(head.next)的下一个节点(next)变为1(head).
    head.next = null;//将1(head)的下一个节点变为null.
    return newLinkedList;
}