LeedCode_Num206_反转链表

题目要求：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解法一

新建一个链表，然后从原链表的头结点开始遍历，把每个元素头插进新的链表，最后返回新链表的头结点

public ListNode reverseList(ListNode head) {    if(head == null || head.next == null){      //如果头结点为空，或者只有一个结点，则没必要反转 return head;    }    ListNode node = head;    ListNode newNode = null;//存储新链表的头结点    while(node != null){      //把原链表的每一个元素都插入到新链表的第一个位置 newNode = new ListNode(node.val, newNode); node = node.next;    }    return newNode;//返回新链表的头结点}

时间复杂度和空间复杂度都是O(n)

解法二

利用迭代解决：用三个指针，cur指向结点，prev指向结点的前驱，next保存后继结点的地址

使cur.next指向prev，然后后移重复上述操作

代码实现：

public ListNode reverseList(ListNode head) {    if(head == null || head.next == null){ return head;    }    ListNode prev = null;//保存前驱结点    ListNode cur = head;//待反转结点    while(cur != null){ ListNode next = cur.next;//在循环内部定义，确保next不会空指针访问 cur.next = prev;//反转 prev = cur; cur = next;    }  //循环结束后prev正好停在最后一个结点，返回prev即可    return prev;}

时间复杂度O(n)、空间复杂度O(1)

解法三

递归解决问题

该递归方法的语义即作用是：传入一个链表的头结点，返回反转后的链表的头结点

当前我们只知道头结点head，如果头结点为空或者只有一个头结点，则无需反转，直接返回，否则保存头结点的后继结点node，然后把头结点之后的结点head.next作为子链表交给递归方法解决，返回值用新的头结点接收

接着把头结点head接在原后继结点node后面，这里有一点需要注意，head.next依然是node，因此我们需要把这个连接断开，否则链表为空

最后返回新的头结点即可

public ListNode reverseList(ListNode head) {    if(head == null || head.next == null){ return head;    }    ListNode node = head.next;    ListNode newHead = reverseList(head.next);    node.next = head;    head.next = null;//断开头结点后node的连接    return newHead;}