力扣206反转链表 头插法 Java版本

题目

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

思路

采用头插法,相当于把节点从前往后一个个拿下来然后插入到新链表的第一个节点前边

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //如果是空链，则直接返回空
        if (head==null){
            return null;
        }
        //采用头插法,相当于把节点从前往后一个个拿下来然后插入到新链表的第一个节点前边
        //先创建一个新的虚拟头节点用来生成新的链
        ListNode dummyHead = new ListNode();
        dummyHead.next=null;
        //定义一个负责遍历的节点
        ListNode r=head;
        //再定义一个节点在r后面一个位置，防止断链找不到后边的节点
        ListNode latter = r.next;
        //下面就是要把r一个个头插到新的链表
        while (r!=null){
            r.next = dummyHead.next;
            dummyHead.next =r;
            r=latter;
            if(latter!=null){
                latter = latter.next;
            }
        }
        return dummyHead.next;
    }
}