8.链表(LinkedList)

链表的反转

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