leetcode热题100学习计划-链表-反转链表

思路

使用头插法逆转链表

注：链表一般为操作方便，头结点不存值，是一个虚拟节点

代码

/**
 * 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) {
        //使用头插法
        
        //虚拟节点，
        ListNode dummynode=new ListNode(0);

        dummynode.next=null;

        ListNode curr = head;
        ListNode q=null;
        while (curr != null) {
            //把第一个结点保存一下
            q=dummynode.next;
            //把当前结点接在虚拟节点后面
            dummynode.next=curr;
            //当前结点移到下一个结点
            curr=curr.next;
            //把之前的拼回去
            dummynode.next.next=q;
        }
        return dummynode.next;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36