206. 反转链表

Contents

1. 1. 题目
2. 2. 解题

题目

题意：反转一个单链表。

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

解题

思路1 通过虚拟头节点+头插法，便利链表，头插入就是倒序

/**
 * 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 head;
        }
        ListNode sentry = new ListNode(0);
        while(head != null){
            ListNode oneNode = new ListNode(head.val, sentry.next);
            sentry.next = oneNode;
            head = head.next;
        }
        return sentry.next;
    }
}

思路2
看解题思路，双指针反插法，更节省空间

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while(cur!= null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}