102. Linked List Cycle

对于带环链表的检测，效率较高且易于实现的一种方式为使用快慢指针。快指针每次走两步，慢指针每次走一步，如果快慢指针相遇(快慢指针所指内存为同一区域)则有环，否 则快指针会一直走到NULL为止退出循环，返回false.

public boolean hasCycle(ListNode head) {
        // write your code here
        if (head == null || head.next == null) {
            return false;
        }
       
        ListNode slow = head;
        ListNode fast = head;
       
        fast = fast.next.next;
        while(slow != fast) {
            if(fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
       
        return true;
    }

170. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

Wrong solution 1:
public ListNode rotateRight(ListNode head, int k) {
        // write your code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        fast.next = head;
        head = slow.next;
        slow.next = null;
        
        return head;

    }


WA

if k is greater than the length of the linked list, it needs to mod the length of the linked list


Solution 2:
  public ListNode rotateRight(ListNode head, int k) {
        // write your code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;//new ListNode(0);
        //slow.next = head;
        ListNode fast = head;
        int length = getLength(head);
        for (int i = 0; i < (k % length); i++) {
            fast = fast.next;
        }
        
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        fast.next = head;
        head = slow.next;
        slow.next = null;
        return head;
    }
    
    private int getLength(ListNode head) {
        int length = 0;
        ListNode dummy = head;
        while(dummy != null) {
            length++;
            dummy = dummy.next;
        }
        return length;
    }

    

35. Reverse Linked list

Reverse a linked list.

public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp; 
        }
        
        return prev;

    }

96. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Solution:

Create a small list and a large list.

Go through the linked list.

If the current node is smaller than x, we link it with the small list.

Otherwise we link the node with the large list.

Finally, we link the small list with the large list.



WA:

1->4->3->2->5->2->null
3

lcur.next = null;
加入后可行， 这个是为了避免产生环

public class Solution {
    /*
     * @param head: The first node of linked list
     * @param x: An integer
     * @return: A ListNode
     */
    public ListNode partition(ListNode head, int x) {
        // write your code here
        ListNode small = new ListNode(-1);
        ListNode scur  = small;
        ListNode large = new ListNode(-1);
        ListNode lcur  = large;
        ListNode dummy = head;
       
        while (dummy != null) {
            if(dummy.val < x){
                scur.next = dummy;
                scur = scur.next;
            } else {
                lcur.next = dummy;
                lcur = lcur.next;
            }
            dummy = dummy.next;
        }
       
        lcur.next = null; // avoid cycle
        scur.next = large.next;
        return small.next;
    }
}

112. Remove Duplicates from Sorted List

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param head: head is the head of the linked list
     * @return: head of linked list
     */
    public ListNode deleteDuplicates(ListNode head) {
        // write your code here
        if (head == null || head.next == null){
            return head;
        }
       
        ListNode curr = head;
        while(curr.next != null) {
            int val = curr.val;
            if (curr.next.val == val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
       
        return head;
    }
}

165. Merge Two Sorted Lists

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param l1: ListNode l1 is the head of the linked list
     * @param l2: ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // write your code here
        if (l1 == null) {
            return l2;
        }
       
        if (l2 == null) {
            return l1;
        }
       
        // int val = l1.val < l2.val ? l1.val : l2.val;
        ListNode head = new ListNode(-1);
        ListNode dummy1 = l1;
        ListNode dummy2 = l2;
        ListNode dummy3 = head;

        // dummy != null 不是dummy.next != null
        while (dummy1 != null && dummy2 != null){
            if(dummy1.val < dummy2.val){
                dummy3.next = new ListNode(dummy1.val);
                dummy1 = dummy1.next;
            } else {
                dummy3.next = new ListNode(dummy2.val);
                dummy2 = dummy2.next;
            }
            dummy3 = dummy3.next;
        }
       
        // 如果是dummy.next == null 那就不会进入这个判断了
        if (dummy1 == null) {
            dummy3.next = dummy2;
        } else {
            dummy3.next = dummy1;
        }
       
        return head.next;
    }
}

174. Remove Nth Node From End of List

public class Solution {
    /*
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: The head of linked list.
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // write your code here
        // slow is point before target, fast gonna reach the end of list
        ListNode slow = head;
        ListNode fast = head;
       
        // There is n nodes between slow and fast
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
       
        // Case: 1->null 1,  1->2->null 2
        if(fast == null) {
            head = head.next;
            return head;
        }
       
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
       
        if (slow == head) {
            head = head.next;
        } else {
            slow.next = slow.next.next;
        }
       
        return head;
    }
}

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: The head of linked list.
     */
    ListNode removeNthFromEnd(ListNode head, int n) {
        // write your code here
        if (head == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy.next;
        
        ListNode p1 = dummy;
        ListNode p2 = dummy;
        
        for (int i = 0; i < n; i++) {
            p1 = p1.next;
        }
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p2.next = p2.next.next;
        
        return dummy.next;
    }
}