链表面试常考题目—链表逆序 链表逆序操作

链表逆序，是力扣第206道题，属于easy级别。
https://leetcode-cn.com/problems/reverse-linked-list/

题目描述：
反转一个单链表。

示例:

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

链表基础知识

public class ListNode {
    public Object value;
    public ListNode next;
    public ListNode(Object value) {
        this.value = value;
    }
}

value存储在链表中的值，next指向下一个节点。

先来一道简单的题目，认识下链表：
（1）定义5个节点；（2）将这5个节点连接起来；（3）定义5个节点；

 public static void main(String[] args) {
        //1、定义5个节点
        ListNode node0 = new ListNode(10);
        ListNode node1 = new ListNode(20);
        ListNode node2 = new ListNode(30);
        ListNode node3 = new ListNode(40);
        ListNode node4 = new ListNode(50);
        //2、将5个节点穿起来
        node0.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;
        //3、遍历链表
        ListNode head = node0;
        while(head != null){
            System.out.println(head.value);
            head = head.next;
        }
    }

链表逆序的基本思路
依次遍历链表节点，每遍历一个节点就反转一个节点。

原始结构中，首先定义一个新的链表节点 new_head。

第一次循环，我们把节点1(head)和new_head串起来，即 head.next = new_head 。但是在这之前，我们需要先把原始链表中节点1(head)的next指针(节点2)保存下来，然后把节点2变成原始链表的head节点。

代码实现：

public class Solution {
    public ListNode reverseList(ListNode head) {
        //新链表的头结点
        ListNode newHead = null;
        while(head != null){
            //备份原始链表head节点的下一个节点
            ListNode temp = head.next;
            //把新链表的头结点和原始链表头节点串起来
            head.next = newHead;
            //将原始链表的头结点变成新链接的头节点
            newHead = head;
            //将第一步备份的原始头结点的下一个节点变成原始链表头结点
            head = temp;
        }
        return newHead;
    }
}

简单说，就是要先备份下一个节点，将原始头结点和新头节点串起来，再角色互换，原始链表头结点变成新链表头结点。