当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.206.Reverse Linked List

LeetCode.206.Reverse Linked List


题目描述

Reverse a singly linked list.

Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?


解题过程

逆置单链表,非常经典的面试题,是必须滚瓜烂熟的。

使用头结点的循环头插法

我印象中有不加头结点的方法,但长时间不做题有点儿乱,想不明白,自己先尝试写了个在前面加额外头结点的方法,调试几次通过了:

//使用一个新申请的头结点
public ListNode reverseList0(ListNode head) {
    if(head==null)
        return head;
    ListNode tempHead = new ListNode(0);//头结点
    tempHead.next = head;
    ListNode cur = head.next;
    head.next = null;
    while(cur!=null) {
        ListNode curNext = cur.next;//curNext保存当前结点的下一个结点
        cur.next = tempHead.next;//当前结点插入到新链表头结点之后
        tempHead.next = cur;
        cur = curNext; //cur继续指向原链表下一个结点
    }
    return tempHead.next;
}

不使用头结点的循环头插法

看网上的解法,常见的有两种,一种是循环头插法(包括使用头结点的和不使用头结点的),一种是递归,其中不使用头结点的原地逆置如下:

//原地逆置(不使用额外的头结点)
public ListNode reverseList1(ListNode head) {
    if(head == null)
        return head;
    ListNode cur = head.next; //cur:当前结点
    head.next = null; //head:逆置后链表的首节点,初始时是原链表的首节点(逆置后的末结点)所以next设为null
    while(cur != null){
        ListNode curNext = cur.next; //curNext:保存当前结点的下一个结点
        cur.next = head; //当前结点成为新链表表头(新链表表头挂到当前结点后)
        head = cur; //head指向新链表表头
        cur = curNext; //cur继续指向原链表下一个结点
    }
    return head;
}

还有一种写法如下,更简洁:

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

递归逆置单链表

递归法的思路是这样的:把链表看成两部分,当前表头结点head和剩下所有结点head.next,递归对剩下所有结点进行逆置得子链表newHead,然后把头结点接到逆置后的子链表newHead尾部即可

//递归逆置
public ListNode reverseList(ListNode head) {
    if(head==null || head.next==null)//链表为空或只有一个结点时结束
        return head;
    ListNode newHead = reverseList(head.next);//递归逆置head.next,newHead为逆置后的新链表
    head.next.next = head; //head.next是逆置后子链表newHead的最后一个结点
    head.next = null;
    return newHead;
}

这里注意,对head.next调用reverseList()后,head.next就是逆置后子链表newHead的最后一个结点,一开始我也没想到,不知道如何获得逆置后子链表的最后一个结点,其实如果改为下面这种写法会更好理解:

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

        ListNode next = head.next; //用next保存剩余部分的首结点(逆置后成尾结点)
        ListNode newHead = reverseList(next);
        next.next = head;
        head.next = null;

        return newHead;
    }
}

用next保存剩余部分的首结点,则逆置后自然成为返回的子链表的末尾结点


GitHub代码


上一篇 LeetCode.009.Palindrome Number

下一篇 LeetCode.003.Longest Substring Without Repeating Characters

阅读
797
阅读预计3分钟
创建日期 2018-02-05
修改日期 2018-02-06
类别
百度推荐