Linked List

基本操作

LC21. Merge Two Sorted Lists

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val){
                head.next = l1;
                l1 = l1.next;
            } else {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }
         if (l1 == null) {
             head.next = l2; 
             } else if (l2 == null){
             head.next = l1;   
         }
        return dummy.next;
    }

链表删除

LC83. Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
      ListNode cur = head;
        while (cur.next != null){
            if (cur.val == cur.next.val){
                cur.next = cur.next.next; 
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

LC82. Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list
Input: 1->1->1->2->3
Output: 2->3

//一般头文件可能被删除的情况可以用dummy来做。
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
             ListNode dummy = new ListNode(0);
             dummy.next = head;
             ListNode prev = dummy;
        
        while (prev.next != null && prev.next.next!= null){
            if (prev.next.val == prev.next.next.val){
                int val = prev.next.val;
                while (prev.next != null && prev.next.val == val)
                    prev.next = prev.next.next;;// 在这个循环里prev.next永远都是从prev指来的，prev从来没有变过。所以prev.next永远都往下指。
            } else {
                prev = prev.next;
            }
        }
        return dummy.next;
    }
}

LC203. Remove-linked-list-elements
Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

public ListNode removeElements(ListNode head, int val) {
        ListNode root = new ListNode(1);
        root.next = head;     // next of root is head; ListNode root -> ListNode head 
        ListNode pre = root; //pre is a pointer, which point to head of new root
        while (pre.next != null){
            if (pre.next.val == val)
                pre.next = pre.next.next;
            else {
                pre = pre.next;
            }
        }
        return root.next; // alway return the linked list root, not pre. pre is only pointer
    }

LC19. Remove Nth Node From End of List
Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

 public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        //scan the fast pointer to (n-1)th element
        for (int i = 1; i <= n; i++){
            fast = fast.next;
        }
        //move the two pointers together and find the back N element
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        // delete the required element
        slow.next = slow.next.next;
        return dummy.next;
    }

LC237. Delete Node in a Linked List
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list
should become 4 -> 5 -> 9 after calling your function.

  public void deleteNode(ListNode node) {
        if (node == null) {
            return;
        }
        node.val = node.next.val;
        node.next = node.next.next;
    }

链表反转与旋转

LC206 Reverse Linked List

// 1-2-3-4-null
// null-1    2-3-4-null
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode newHead = null;
        ListNode temp = null;
        while(head != null){
            temp = head.next;// create a temp to stroe head.next address(store 2)
            head.next = newHead; // head.next can point to prev address after store head.next address(1 point to null)
            newHead = head;//  prev pointers point to head for next iteration()
            head = temp; 
        }
        return newHead;
    }
}

LC92. Reverse Linked List II
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        for (int i = 1; i < m; i++){
            if (prev==null) return null;
            prev = prev.next;
        }
        ListNode premNode = prev;
        ListNode mNode = prev.next;
        
        ListNode nNode = mNode;
        ListNode postnNode = mNode.next;
        for (int i = m; i < n; i++){
            if(postnNode == null) return null;
            ListNode temp = postnNode.next;
            postnNode.next = nNode;
            nNode = postnNode;
            postnNode = temp;
        }
        premNode.next = nNode;
        mNode.next = postnNode;
        return dummy.next;
    }

LC24. Swap Nodes in Pairs
Given 1->2->3->4, you should return the list as 2->1->4->3.

public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        while(prev.next != null && prev.next.next != null){
            ListNode temp1 = prev.next; //store 1 address
            ListNode temp2 = prev.next.next; // store 2 address
            temp1.next = temp2.next;// 1 point to 3
            prev.next = temp2; // prev.next point to temp2 address
            prev.next.next = temp1;// prev.next.next point to temp1 address
            prev = prev.next.next;// prev move to next position for iteration
        }
        return dummy.next;
    }

LC61. Rotate List
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

// first we calculate k % length_linkedlist, that is how many elements we would need to  move
 public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        int i;
        for (i = 0; fast.next != null; i++){ // get the whole length of list
            fast = fast.next;
        }
        for (int j = 0; j < i - k % i; j++){
            slow = slow.next; // get the partition element;
        }
       fast.next = dummy.next; //先把dummy.next清空才能放进来
       dummy.next = slow.next;
        slow.next = null;

        return dummy.next;
    }

LC24. Swap Nodes in Pairs
Given 1->2->3->4, you should return the list as 2->1->4->3.

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        while(prev.next != null && prev.next.next != null){
            ListNode temp1 = prev.next; //store 1 address
            ListNode temp2 = prev.next.next; // store 2 address
            temp1.next = temp2.next;// 1 point to 3
            prev.next = temp2; // prev.next point to temp2 address
            prev.next.next = temp1;// prev.next.next point to temp1 address
            prev = prev.next.next;// prev move to next position for iteration
        }
        return dummy.next;
    }
}

LC25. Reverse Nodes in k-Group
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

LC86. Partition List
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

 public ListNode partition(ListNode head, int x) {
        //做两个dummy list，分别判断小于就放左边，大就放右边，最后一步记得把右的next设置为null
        if (head == null) return null;
        ListNode leftDummy = new ListNode(0);
        ListNode rightDummy = new ListNode(0);
        ListNode left = leftDummy;
        ListNode right = rightDummy;
        while(head != null){
            if(head.val < x){
                left.next = head;
                left = left.next;
            } else {
                right.next = head;
                right = right.next;
            }
            head = head.next;
        }
        right.next = null;
        left.next = rightDummy.next;
        return leftDummy.next; 
    }

LC138. Copy List with Random Pointer

 public RandomListNode copyRandomList(RandomListNode head) {
         if (head == null) return null;
  
  Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
  
  // loop 1. copy all the nodes
  RandomListNode node = head;
  while (node != null) {
    map.put(node, new RandomListNode(node.label));
    node = node.next;
  }
  
  // loop 2. assign next and random pointers
  node = head;
  while (node != null) {
    map.get(node).next = map.get(node.next);
    map.get(node).random = map.get(node.random);
    node = node.next;
  }
  
  return map.get(head);

    }

LC141. LinkedList Cycle

 public boolean hasCycle(ListNode head) {
        
        ListNode pfast = head;
        ListNode pslow = head;
        while (pfast != null && pfast.next != null){
        pfast = pfast.next.next;
        pslow = pslow.next;
        
        if (pfast == pslow){
            return true;
        } 
    }
        return false;
    }

LC141. LinkedList Cycle II

/ 做法就是先判断是不是有环，有环之后，将其中一个指针回到head，和相遇点那个指针一起移动，碰到的地方就是环的起始点。 a+x /1 = a+x+b+x /2 a = b
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != slow){
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        }
        while (head != slow.next){
            slow = slow.next;
            head = head.next;
        }
        return head;
    }
}

LC143. Reorder List
Given 1->2->3->4, reorder it to 1->4->2->3.
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

// 先找到中点，再把中点后的reverse一下,最后merge
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return ; // notice 边界条件
        ListNode middle = findMiddle(head);
        ListNode left = reverse(middle.next);
        middle.next = null;//断开连接
        ListNode right = head;
        merge(right, left);
    }
    private ListNode reverse(ListNode head){
        ListNode prev = null;
        while (head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    private ListNode findMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next!= null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    private ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        int count = 1;
        while (l1 != null && l2 !=null){
            if(count % 2 != 0){
                head.next = l1;
                l1 = l1.next;
            } else {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
            count++;
        }
        if (l1 != null){
            head.next = l1;
        } else if (l2 != null){
            head.next = l2;
        }
        return dummy.next;
    }
}

LC148. Sort List
Input: 4->2->1->3
Output: 1->2->3->4

 public ListNode sortList(ListNode head) {
       if(head == null || head.next == null) return head;
       ListNode mid = findMiddle(head);
       ListNode right = sortList(mid.next);
       mid.next = null;//此处是为了让右半边的链表断开到mid结束。
       ListNode left = sortList(head);
       return merge(left, right);
        
    }
    // find middle point
    private ListNode findMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;// 当出现..next时候，前两个必须一一判断是否为空
        }    
        return slow;
    }
    // merge sorting list
    private ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                head.next = l1;
                l1 = l1.next;
            } else {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }
        if (l1 != null){
            head.next = l1;
        } else if (l2 != null){
            head.next = l2;
        }
        return dummy.next;
    }

LC328. Odd Even Linked List
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

 public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenH = even;
        while (even != null && even.next != null){
            odd.next = odd.next.next;//有顺序的不然地址会丢失。
            even.next = even.next.next;
            even = even.next;
            odd = odd.next;
        }
        odd.next = evenH;
        return head;
    }

LC160. Intersection of Two Linked
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        int lenA= getLength(headA), lenB= getLength(headB);
        if (lenA > lenB) {
            for (int i =0; i< lenA - lenB; i++) headA = headA.next;
        } else {
            for (int i =0; i< lenB - lenA; i++) headB = headB.next;
        } 
        while (headA != null && headB != null && headA != headB){
            headA = headA.next;
            headB = headB.next;
        }
        if (headA != null && headB != null){
            return headA;
        } else {
            return null;
        }
     }
        
        public int getLength(ListNode head){
            int count = 0;
            while (head != null){
                count++;
                head = head.next;
            }
            return count;
        }

LC234. Palindrome Linked List
Input: 1->2->2->1
Output: true

 public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        
        ListNode slow = head;
        ListNode fast = head;
        /*find middle point of liked list*/
        while (fast != null && fast.next !=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tail = reverseList(slow);
        while (head != slow) {
            if (head.val != tail.val) {return false;}
            head = head.next;
            tail = tail.next;
        }
        return true;
    }
    
    public ListNode reverseList(ListNode head){
        ListNode p = head, newHead = null;
        while (p!= null){
            ListNode temp = p.next;
            p.next = newHead;
            newHead = p;
            p = temp;
        }
        return newHead;
        
    }