206. 反转链表

一、题目描述

反转一个单链表。

示例:

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

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

二、解题思路

一、递归法

1、解题思路

1. 链表专用判断，head为空或后继节点为空则可直接返回
2. 声明head后继节点的引用变量next，避免在递归过程中失去指向
3. 后继节点以步骤1、2递归，直至head节点的执向为空则返回
4. 递归返回中的返回节点为newHead(新的头节点)
5. 改变head、next节点指向，next.next-->head head.next-->null
6. 每次递归函数执行完毕，返回newHead

2、代码

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

二、头插法

1、解题思路

1. 链表专用判断，head为空或后继节点为空则可直接返回
2. 新建一个虚拟头节点dummyHead，作为被移动节点的前驱
3. 进入循环，循环条件为head != null
4. 声明head后继节点的引用变量next，暂存head后继节点
5. head-->dummyHead.next;dummyHead.next-->head;head-->next
6. 结束循环后，返回虚拟节点的后继节点

2、代码

    public ListNode reverseList(ListNode head) {
       if(head == null||head.next == null)return head;
        ListNode dummyHead = new ListNode(-1);//作为中转节点
        while(head!= null){
            ListNode next = head.next;
            head.next = dummyHead.next;
            dummyHead.next = head;
            head = next;
        }

        return dummyHead.next;
    }

三、前中后法

1、解题思路

1. 链表专用判断，head为空或后继节点为空则可直接返回
2. 声明pre、cur、latter节点，pre-->null,cur-->head
3. 进入循环，循环条件为cur != null
4. 声明cur后继节点的引用变量latter，暂存cur后继节点
5. cur.next-->pre;pre=cur;cur=latter;
6. 循环结束后，返回pre节点

2、代码

    public ListNode reverseList(ListNode head) {
       if(head == null||head.next == null)return head;
        ListNode pre =null;
        ListNode cur =head;
        while(cur!= null){
            ListNode latter =cur.next;
            cur.next = pre;
            pre = cur;
            cur = latter;
        }
        return pre;
    }