06.将单链表反转

目录介绍

01.题目要求
02.问题分析
03.实例代码

01.题目要求

输入一个链表，反转链表后，输出链表的所有元素。
```
例如链表：1->2->3->4
反转之后：4->3->2->1
```

02.问题分析

2.1 一句话概括

从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O（n）

2.2 解题思路

链表的很常规的一道题，这一道题思路不算难，但自己实现起来真的可能会感觉无从下手，参考了别人的代码。
思路就是我们根据链表的特点，前一个节点指向下一个节点的特点，把后面的节点移到前面来。
就比如下图：我们把1节点和2节点互换位置，然后再将3节点指向2节点，4节点指向3节点，这样以来下面的链表就被反转了。
- 链表

2.3 解题方法

①遍历。将指向下一个节点的指针指向上一个节点。
②递归。先让指向下一个节点的指针为空，然后递归调用，最后再将指向下一个节点的指针指向上一个节点。

03.实例代码

3.1 代码如下所示

代码如下

public class LinkList {
    public Node head;
    public Node current;
    
    class Node {
        //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
        int data; //数据域
        Node next;//指针域
        public Node(int data) {
            this.data = data;
        }
    }
    
    //方法：向链表中添加数据
    public void add(int data) {
        //判断链表为空的时候
        if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
            head = new Node(data);
            current = head;
        } else {
            //创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
            current.next = new Node(data);
            //把链表的当前索引向后移动一位
            current = current.next;   //此步操作完成之后，current结点指向新添加的那个结点
        }
    }

    //方法：链表的反转
    public Node reverseList(Node head) {

        //如果链表为空或者只有一个节点，无需反转，直接返回原链表的头结点
        if (head == null || head.next == null) {
            return head;
        }

        Node current = head;
        Node next = null; //定义当前结点的下一个结点
        Node reverseHead = null;  //反转后新链表的表头

        while (current != null) {
            next = current.next;  //暂时保存住当前结点的下一个结点，因为下一次要用

            current.next = reverseHead; //将current的下一个结点指向新链表的头结点
            reverseHead = current;  

            current = next;   // 操作结束后，current节点后移
        }

        return reverseHead;
    }
}

测试方法

public static void main(String[] args) {
    ListNode a = new ListNode(1);
    ListNode b = new ListNode(2);
    ListNode c = new ListNode(3);
    ListNode d = new ListNode(4);
    ListNode e = new ListNode(5);
    a.next = b;
    b.next = c;
    c.next = d;
    d.next = e;
    Node e = new LinkList().ReverseList(a);
    while (e != null) {
      System.out.println(e.val);
      e = e.next;
    }
}

结果如下所示
```
5
4
3
2
1
```

遍历

/**
 * 反转单链表
 * @param head
 * @return
 */
private static Node reverseHead(Node head) {
    if (head == null) {
        return head;
    }
    Node pre = head;
    Node cur = head.nextNode;
    Node next = null;
    while(cur != null){
        next = cur.nextNode;
        cur.nextNode = pre;
        pre = cur;
        cur = next;
    }
    head.nextNode = null;
    head = pre;
    return head;
}

递归

/**
 * 递归反转
 * @param head
 * @return
 */
private static Node reverseByRecur(Node current) {
    if (current == null || current.nextNode == null) return current;  
     Node nextNode = current.nextNode;  
     current.nextNode = null;  
     Node reverseRest = reverseByRecur(nextNode);  
     nextNode.nextNode = current;  
     return reverseRest;  
}