206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

题目要求

反转一个表，表尾到表头

思路

设置一个头结点前驱，设置一个指针指向第二个元素，则每一次都将指针指向的元素插入前驱和头结点之间，即完成了反转。

代码

public ListNode reverseList(ListNode head) {
        if (head==null) {
            return head;
        }
        ListNode headPre =new ListNode(0);
        headPre.next=head;//前驱节点
        ListNode q = head.next;//遍历指针
        head.next=null;//头节点会成为最后一个元素，所以可以指向空了
        
        while (q!=null) {//插入
            ListNode temp =q.next;
            q.next=headPre.next;
            headPre.next=q;
            q=temp;
        }
        
        return headPre.next;//返回头节点

    }

思路2（来源网络）

首先定义一个前驱为空prev=null；
用一个节点next保存head的nextcur=head;next=cur.next；
将头节点next指向前驱。cur.next=prev
令前驱等于cur，cur等于nextprev=cur;cur=next
循环此步骤
最后prev就是最后一个元素

代码

public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        
        return prev;
    }