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;
}
}