206. 反转链表

206. Reverse Linked List

题目描述

反转一个单链表。

每日一算法2019/5/19Day 16LeetCode206. Reverse Linked List

示例:

进阶:

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

Java 实现

ListNode 类

class ListNode {

    int val;

    ListNode next;

    ListNode(int x) {

        val = x;

    }

    @Override

    public String toString() {

        return val + "->" + next;

    }

}

Iterative Solution

class Solution {

    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;

    }

}

Recursive Solution

class Solution {

    public ListNode reverseList(ListNode head) {

        if (head == null || head.next == null) {

            return head;

        }

        ListNode p = reverseList(head.next);

        head.next.next = head;

        head.next = null;

        return p;

    }

}

测试类

public class Test {

    public static void main(String[] args) {

        ListNode head = new ListNode(1);

        ListNode a = new ListNode(2);

        ListNode b = new ListNode(3);

        ListNode c = new ListNode(4);

        ListNode d = new ListNode(5);

        head.next = a;

        a.next = b;

        b.next = c;

        c.next = d;

        System.out.println(head);

        System.out.println(new Solution().reverseList(head));

    }

}

运行结果

Iterative Solution

Recursive Solution

相似题目

• 92. 反转链表 II
• 156. 上下翻转二叉树
• 234. 回文链表

参考资料

• https://leetcode-cn.com/problems/reverse-linked-list/
• https://leetcode.com/problems/reverse-linked-list/