206. Reverse Linked List(Easy)

题目地址

Reverse a singly linked list.Example:Input: 1->2->3->4->5->NULLOutput: 5->4->3->2->1->NULLFollow up:A linked list can be reversed either iteratively or recursively. Could you implement both?

solution

题意是给定一个链表，要求将链表反转，且需要分别用迭代和递归实现。

解法一：迭代

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode reverseList(ListNode head) {        ListNode start = new ListNode(-1);        ListNode p ,temp;        while (head != null)        {            p = head.next;            temp = start.next;            start.next = head;            head.next = temp;            head = p;        }        return start.next;    }}

解析：构造一个额外的头结点，用链表的头插法即可搞定。

解法二：递归

class Solution {    public ListNode reverseList(ListNode head) {        if (head == null || head.next == null)  //链表为空或当前结点的下一个结点为空即返回head            return head;        ListNode p = reverseList(head.next);  //新链表的头结点        head.next.next = head;                //将当前结点的下一个结点的下一个个结点置为head，即反转        head.next = null;    //断掉head结点与下一个结点的连接        return p;            //返回头结点    }}

解析：首先判断链表为空或当前结点的下一个结点为空即返回head，否则递归访问链表；当递归条件不满足时，返回新链表的头结点，并将头结点赋值给p，即p成为新链表的头结点。此时，将当前结点的下一个结点的下一个结点置为head，即翻转，然后断掉head结点与下一个结点的连接，最后返回头结点p。

reference

Notes

1.递归算法的逻辑不太好想清楚，得仔细推敲！