链表的反转
solution1
//time complexity:O(n),space complexity:O(1)
public ListNode reverse(ListNode head) {
if(head == null || head.next == null)return head;
ListNode pre = null, curr = head, next = null;
while(curr!=null){
next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
solution2
//time complexity:O(n),space complexity:O(n)
public ListNode reverse(ListNode head) {
if(head == null || head.next == null)return head;
ListNode newNode = reverse(head.next);
ListNode tail = head.next;
tail.next = head;
head.next = null;
return newNode;
}
快慢指针:
1.给定一个链表，如何找到链表的中间点？
思想：Slow指针每次走一步，Fast指针每次走两步，当Fast指针到头的时候Slow恰好停在中点。
/**
* class ListNode {
* public int value;
* public ListNode next;
* public ListNode(int value) {
* this.value = value;
* next = null;
* }
* }
*/
public ListNode middleNode(ListNode head) {
if(head == null || head.next == null)return head;
ListNode slow = head;
ListNode fast = head;
while(fast.next!=null&&fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//OR
public ListNode middleNode(ListNode head) {
if(head == null || head.next == null)return head;
ListNode slow = head;
ListNode fast = head;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
2.判断一个LinkedList是否有环。
思路：Slow指针每次走一步，Fast指针每次走两步，两者速度差是1，如果链表存在环则Fast肯定会追上Slow。
/**
* class ListNode {
* public int value;
* public ListNode next;
* public ListNode(int value) {
* this.value = value;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null||head.next==null)return false;
ListNode slow=head, fast=head;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
3.Insert a value in a sorted linked list.给定一个sorted好的链表和一个value值,将value值插入到链表正确的位置。
/**
* class ListNode {
* public int value;
* public ListNode next;
* public ListNode(int value) {
* this.value = value;
* next = null;
* }
* }
*/
public class Solution {
//tiem complexity:O(n); space complexity:O(1)
public ListNode insert(ListNode head, int value) {
//corner case
ListNode node = new ListNode(value);
if(head == null || head.value >= value){
node.next = head;
return node;
}
ListNode prev = null;
ListNode curr = head;
while(curr!=null){
if(curr.value < value){
prev = curr;
curr = curr.next;
}else{
break;
}
}
prev.next = node;
node.next = curr;
return head;
}
}
4.Merge two sorted lists into one large sorted list.合并两个排序好的链表
/**
* class ListNode {
* public int value;
* public ListNode next;
* public ListNode(int value) {
* this.value = value;
* next = null;
* }
* }
*/
public class Solution {
//tiem complexity:O(n); space complexity:O(1)
public ListNode merge(ListNode one, ListNode two) {
if(one == null)return two;
if(two == null)return one;
ListNode curr1 = one;
ListNode curr2 = two;
ListNode head = new ListNode(0);
ListNode curr = head;
while(curr1!=null&&curr2!=null){
if(curr1.value<=curr2.value){
curr.next = curr1;
curr1=curr1.next;
}else{
curr.next = curr2;
curr2 = curr2.next;
}
curr = curr.next;
}
if(curr1!=null){
curr.next = curr1;
}
if(curr2!=null){
curr.next = curr2;
}
return head.next;
}
}
5.Linkedlist Partition给定一个链表和一个目标值t，将其划分为所有小于T的节点在大于或等于目标值T的节点之前列出，应该保留两个分区中每个节点的原始相对顺序。L = 2 -> 4 -> 3 -> 5 -> 1 -> null, T = 3, is partitioned to 2 -> 1 -> 4 -> 3 -> 5 -> null
/**
* class ListNode {
* public int value;
* public ListNode next;
* public ListNode(int value) {
* this.value = value;
* next = null;
* }
* }
*/
public class Solution {
//tiem complexity:O(n); space complexity:O(1)
public ListNode partition(ListNode head, int target) {
if(head == null)return head;
ListNode dummyNode1 = new ListNode(0);
ListNode dummyNode2 = new ListNode(0);
ListNode curr = head;
ListNode curr1 = dummyNode1;
ListNode curr2 = dummyNode2;
while(curr!=null){
if(curr.value<target){
curr1.next=curr;
curr1 =curr1.next;
}else{
curr2.next = curr;
curr2 = curr2.next;
}
curr = curr.next;
}
curr1.next = dummyNode2.next;
curr2.next = null;
return dummyNode1.next;
}
}
6.给定一个单链表L: L0→L1→…→Ln-1→Ln,重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2→…必须在不改变节点值的情况下进行原地操作。
思路：
step1:给定的链表是sorted好的，可以将其砍为左右两个链表linked1、linked2,也就是找到mid节点
step2:再将linked2反转
step3:将linked1与linked2按题意合并成一个linkedlist
/**
* class ListNode {
* public int value;
* public ListNode next;
* public ListNode(int value) {
* this.value = value;
* next = null;
* }
* }
*/
public class Solution {
//tiem complexity:O(n); space complexity:O(1)
public ListNode reorder(ListNode head) {
if(head==null||head.next == null)return head;
ListNode mid = findMid(head);
ListNode tail = reverse(mid.next);
mid.next = null;
merge(head, tail);
return head;
}
//tiem complexity:O(n); space complexity:O(1)
private void merge(ListNode head1, ListNode head2){
if(head1==null)return;
if(head2==null)return;
ListNode dummy = new ListNode(0);
int index = 0;
while(head1!=null&&head2!=null){
if(index%2==0){
dummy.next = head1;
head1 = head1.next;
}else{
dummy.next = head2;
head2 = head2.next;
}
index++;
dummy = dummy.next;
}
if(head1!=null){
dummy.next = head1;
}else{
dummy.next = head2;
}
}
//tiem complexity:O(n); space complexity:O(1)
private ListNode reverse(ListNode head) {
if(head == null || head.next == null)return head;
ListNode pre = null, curr = head, next = null;
while(curr!=null){
next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
//tiem complexity:O(n); space complexity:O(1)
private ListNode findMid(ListNode head){
if(head == null || head.next == null)return head;
ListNode slow = head, fast = head;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
