Unit 1 Practice I

237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

//Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 
public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

图示如下：

• Delete Node in Linked List

Unit 2 Practice II

206. Reverse Linked List

Reverse a singly linked list.

Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?

(1) Reverse the linked list iteratively

• reverseLinkedlist.jpg

// Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode reverseList(ListNode head) {
    if (head == null ||head.next == null) {
        return head;
    }
    ListNode pre = head;
    ListNode cur = pre.next;
    
    head.next = null;
    
    while (pre != null && cur != null) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

(2) Reverse the linked list recursively

• ReverseLinkedlistRecursively.jpg
  
  

  举例说明：反转1->2->3->4
  （i）假设1->2->3->4已经反转好，成为4->3->2->1，然后将4->3->2->1看成一个整体，让这个整体的next指向null；
  （ii）假设2->3->4已经反转好，已经成为了4->3->2, 然后将4->3->2看成一个整体，让这个整体的next指向1；
  （iii）接下来问题变成了反转2->3->4
  假设3->4已经反转好，已经成为了4->3, 然后将4->3看成一个整体，让这个整体的next指向2；
  （iv）然后问题变成了反转3->4
  假设4(实际上是4->NULL)已经反转好，已经成为了4(其实是head->4), 然后将4(其实是head->4)看成一个整体，让这个整体的next指向3；
  （v）然后问题变成了反转4，head->4。

// Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode reverseList(ListNode head) {
    if (head == null ||head.next == null) {
        return head;
    }
    ListNode nextNode = head.next;
    head.next = null;
    ListNode rest = reverseList(nextNode);
    nextNode.next = head;
    return rest;
}

Unit 3 Practice III

LeetCode 141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

1. Use two pointers, slower and faster.
2. Slower moves step by step. faster moves two steps at the same time.
3. If the Linked List has a cycle slower and faster will meet at some point.

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

Unit 4 Practice IV

LeetCode 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

1. The key to solve the problem is defining a fake head.
2. Then compare the first elements from each list.
3. Add the smaller one to the merged list.
4. Finally, when one of them is empty, simply append it to the merged list, since it is already sorted.

class ListNode {
    int val; 
    ListNode next;
    ListNode (int x) {
        val = x;
    }
    public static ListNode mergeTwoListNode (ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode result = head;
        while (l1 != null || l2 != null) {
            if (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    result.next = l1;
                    l1 = l1.next;
                }
                else{
                    result.next = l2;
                    l2 = l2.next;
                }
                result = result.next;
            }
            else if (l1 == null) {
                result.next = l2;
                break;
            }
            else if (l2 == null) {
                result.next = l1;
                break;
            }
        }
        return head.next;
    }
    public static void main (String args[]) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);
        l1.next.next.next = new ListNode(7);

        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);
        l2.next.next.next = new ListNode(8);        

        ListNode result = mergeTwoListNode(l1, l2);
        while (result != null) {
            System.out.print (result.val + " ");
            result = result.next;
        }
        System.out.println();
    }
}

Unit 5 Practice V

LeetCode 24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. (意思就是不允许换值)

• SwapNodesInPairs.jpg

class ListNode {
    int val; 
    ListNode next;
    ListNode (int x) {
        val = x;
    }
    public static ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = dummy;
        
        while(head != null && head.next != null){
            node.next = head.next;
            head.next = node.next.next;
            node.next.next = head;
            node = head;
            head = head.next;
        }
        return dummy.next;
    }

    public static void main (String args[]) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);


        ListNode result = swapPairs(head);
        while (result != null) {
            System.out.print (result.val + " ");
            result = result.next;
        }
        System.out.println();
    }
}