2.3 Linked List

链表，主要特性是一个节点一个节点相连。

在Java集合中，常用于实现有序集合LinkedSet，有序列表LinkedList。

在算法题中，常用于实现树形结构。

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

Java Method

add(E e)
add(int index, E element)
remove(int index)
set(int index, E element)
get(int index)

size()
toArray()

Condition

• when doing comparison problems of two linkedlist, there’s generally three conditions to be considered: null, l1 > l2, l1 < l2
• when looping through ListNode(LinkedList)
• use while (node != null) {...} when you are just using this node’s value; and you will stop at the last node + 1 which is a null
• use while (node.next != null) {...} when you are using next node’s value; and you will stop at the last node
• use node = node.next for +1

Pointer

• prevNode
• currNode
• nextNode
• (dummyNode)

Example 1

Problem:

• Given a linked list, remove the nth node from the end of list and return its head.

Solution:

// 首先，如果我知道这个链表多长，假设为k，那么倒数第n个，即为正数第 k-n+1 个
// 其次，另一种解法为快慢节点法，慢节点落后快节点 n 个位置，则当快节点到底，慢节点到倒数 n+1 位
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;

        // move fast n ahead of slow
        for (int i=0; i<n; i++) {
            fast = fast.next;
        }

        // move slow to the (n+1)th node from the end
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // delete the nth node
        slow.next = slow.next.next;

        return dummyHead.next;
    }
}

Example 2

Problem:

• 合并两个有序的链表，不许用额外的空间

Solution:

iterative

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode currentPointer = dummyHead;

        if (l1 == null) return l2;
        if (l2 == null) return l1;

        while (l1!=null && l2!=null) {
            if (l1.val < l2.val) {
                currentPointer.next = l1;
                currentPointer = currentPointer.next;
                l1 = l1.next;
            } else {
                currentPointer.next = l2;
                currentPointer = currentPointer.next;
                l2 = l2.next;
            }
        }

        if (l1 == null) currentPointer.next = l2;
        if (l2 == null) currentPointer.next = l1;

        return dummyHead.next;
    }
}

recursive

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        ListNode mergeHead;
        if(l1.val < l2.val) {
            mergeHead = l1;
            mergeHead.next = mergeTwoLists(l1.next, l2);
        } else{
            mergeHead = l2;
            mergeHead.next = mergeTwoLists(l1, l2.next);
        }
        return mergeHead;
    }
}