关于leetcode个人解题总结:刷题9反转链表

206. 反转链表

有三种解法：利用栈的个性来解，头插法和双指针法

1.利用栈

利用栈后入先出的个性，先把链表的元素全副压入栈中，而后出栈，把每一个出栈的元素插在链表尾部，即可实现反转，能够利用虚构头节点来辅助，指针temp始终指向链表尾部节点，便于尾部插入元素。留神：在尾部插入最初一个元素时，肯定记得在尾部加上null，不然最初元素的next指向倒数第二个元素，呈现循环链表。

class Solution {    public ListNode reverseList(ListNode head) {        if(head == null) return null;        ListNode pre = new ListNode(-1),temp = pre;        Stack<ListNode> st = new Stack<>();        while(head != null){            st.push(head);            head = head.next;        }        while(!st.isEmpty()){            temp.next = st.pop();            temp = temp.next;        }         temp.next = null;        return pre.next;    }}

2.头插法

如果head为空或者只有一个节点，则返回head即可。
设置一个虚构头节点pre，而后将链表从头到尾遍历，每遍历一个元素，将该元素插入在pre和第一个元素之间，须要留神的是，在遍历过程中要用两头变量temp来保留以后元素的下一个节点，以防失落。

class Solution {    public ListNode reverseList(ListNode head) {        if(head == null || head.next == null) return head;        ListNode pre = new ListNode(-1,null);        while(head != null){            ListNode temp = head.next;            head.next = pre.next;            pre.next = head;            head = temp;        }        return pre.next;    }}

3.双指针法

要害：first首先设置为null，用于作为链表反转后的空节点，second指针首先指向head，随后second.next = first,接着first和second指针每次往后挪动一个节点，每次都second.next = first，直到seocnd=null，返回first作为反转链表的头节点。

class Solution {    public ListNode reverseList(ListNode head) {        if(head == null || head.next == null) return head;        ListNode first = null,second = head;        while(second != null){            ListNode temp = second.next;            second.next = first;            first = second;            second = temp;        }        return first;    }}