LinkedList

head, 新旧头节点不能丢失head
.next 来做dereference，null pointer exception的问题需注意
single linked list的最后挂一个null，这个null也是遍历的终止条件

array和single linked list 都是一维的线性结构，区别：

single linked list访问已知index，TC为O(n), array 为O(1)
array是连续存储的，可以根据array的reference算出连续存储的array的内存首地址，然后根据所存的element数据类型和i本身，算出当前要access的element对于array的内存首地址的offset（偏移量），进而直接可以得到我要access element的地址。

int[] arr = null;
int[] arr = new int[0] {} 这个表示arr为空，empty
- null: no object in heap associated with this reference
- empty(length/size() == 0): has object in heap but the object has no valid element
ArrayList<Integer> list = null;
ArrayList<Integer> list = new ArrayList<Integer>(); 这个integer表示size大小

corner case: head == null, head.next == null: 表示list没有或只有一个的
main structure : while loop --> when to exit

Generics只接受class
T can be Integer of characters
Tree? ListNode can also represent TreeNode. --> inplace
- k TreeNode(clarify guarantee k or at most k)

class ListNode<T>{//Generics
    //fields
    T value;
    ListNode next;
    ListNode prev;
    
    // TreeNode[] array; //n size be guatranteed--> Trie
    ArrayList<Node> nerbs; --> size is dynamic change Hashmap
    
    visited; // if visited, set it as true;
    
    
    //methods
    ListNode(int val){
        value = val;
        next = null;
        prev = null;
    }
}

ListNode dummy = new ListNode(0);
- 定位头节点

L206 reverse linked list by one

S0: dummy node
- 把1 2 3 分别插入到dummy后面
S1: iteration
- 遍历到这个node的时候，箭头不向前指，向后指
- demo: while loop先保存next，cur.next = prev; prev = cur; cur = next
- when cur == null, the last node has finished which is prev. so return prev

head(减少head的变量)
null <-- node1 <-- node2 --> node3 --> node4 --> node5 --> node6 --> null
                                                            prev     cur       next

public ListNode reverseLinkedList(ListNode head){
    if(head == null || head.next == null) return head;
    ListNode cur = head;
    ListNode next = null;
    ListNode prev = null;
    
    while(cur != null){
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;

}

S2: recursion **** 这是面试官想要的
- head.next.next = head;
- head.next= null
- TC: O(n)

node1 --> node2 --> node3 --> node4 --> node5 --> node6 --> null
node2 --> node3 --> node4 --> node5 --> node6 --> null
node3 --> node4 --> node5 --> node6 --> null
node4 --> node5 --> node6 --> null
node5 --> <-- node6 --> null        //<-- means head.next.next = head
node6 --> null

public ListNode reverseLinkedList(ListNode head){
    //cc
    if(head == null || head.next == null) return head
    
    ListNode newHead = reverseLinkedList(head.next);
    //wall
    head.next.next = head;
    head.next = null;
    return newHead;
}

S3: Recursion similar to DFS //

public ListNode reverseList(ListNode head){ 
    return reverseLinked(head,null);
}
public ListNode reverseLinked(ListNode head, ListNode newHead){
    if(head == null) return newHead;
    ListNode next = head.next;
    head.next = newHead;
    return reverseLinked(next,head);
}

1.1 L24 25 reverse linked list by pair/ three/ k
- by pair

h
1 --> 2 --> 3 --> 4 --> 5--> 6 --> null
by pair
h
2 --> 1 --> 4 --> 3 --> 6 --> 5--> null

public ListNode reverseByPair(ListNode head){
    if(head == null || head.next == null){ //1
        return head;
    } 
    
    ListNode subHead = reverseByPair(head.next.next); //2
    head.next.next = head; //3
    ListNode newHead = head.next;//4
    head.next= subHead; //5
    return newHead;
    
}

by three / k
- recursion x iteration
- what if not enough node to reverse?
- use two while loop

h
1 --> 2 --> 3 -->   4 --> 5--> 6 --> null
by pair
h
3 --> 2 --> 1 --> 6 --> 5 --> 4--> null

Q1.2 reverse linkedList by range
- range 内 by one reverse

Q2 find middle node(1/2) in LinkedList --> 1/3 1/5 3/7

slow fast two pointers
- if 1/2: fast goes 2 steps, slow goes 1
- 1/3: fast goes 3 steps, slow goes 1
- 3/7: fast goes 7 steps, slow goes 3
1／3 究竟指的是谁，但如果一共7个呢
S1: while loop :fast != null&&fast.next != null
- check if total node num is even
S2: fast.next != null && fast.next.next != nullor s= 0, f = 1, s and f差一步

public ListNode findMid(ListNode head){
    if(head == null || head.next == null){
        return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

2.1 singly linked list, kth position to the right(LC19)
- question: if k> size

Q3 L141 check whether a linkedlist has cycle 2007 第六节1：27

查重／查环的方式：1：31
- 1.hashset
  - 遍历过的node都丢到hashset中
- 2. 加一个visited
  - 新的node设为true
- 3. slow fast pointer, how to set the speed?
  - 两倍速肯定没问题
  - slow第一次到达之前，fast已经check出来
3.0 reverse linkedlist with cycle 1:41:02
- 先clarify带环的linkedlist是什么样的
  - 重复之前的node断开
  - while(cur != null)
  while(!Hashset.contains(cur))
  head.next == null
  !Hashset.contains(head.next)
3.1 L160 intersection of linkedlist 1:48:26
- 找到交叉口
- 从两个head出发往后走，list1list2拥有相同的node
  - 1. Hashset: 放list 1 的listnode 的reference，再找2
  - 2. visited
  - 3. 假如知道list1.size and list2.size，找相遇的node
  - 4. a + b + c = c + b + a
    cur1从h1走完跳回h2走 cur2从h2走完跳回h1走
3.2 return size of cycle 1:59:04
- 先check有没有环，找出入口点
3.3 L142 return enter node of cycle环入口 2:00:43
- 算法解：查重，重复的点就是入口
- 数学解：fast =（a + b)+ n(b+c); slow = a+ b
  - a = (n-1)(b+c) + c
3.4 return kth position after enter node of cycle 2:06:47
- 取余

Q4 Insert a value/node into sorted LinkedList 2:20:08

difference between value and node
- node is like a basket, value is the apple in the basket

L147

1.find the position(think about the head and tail position)

2. need to know prev and cur

prev is required

3. pre processing

S2: no dummy node

in the while loop, use prev.next instead of cur to insert the value in the correct position

public ListNode insertValue(ListNode head, int value){
    ListNode newNode = new ListNode(value);
    if(head == null || value <= head.val){
        newNode.next = head;
        return newNode;
    }
    ListNode prev = head;
    while(prev.next != null || prev.next.val < value){
        prev = prev.next;
    }
    newNode.next = prev.next;
    pre.next = newNode;
    return head;
    
}

L148 Sort List 2:42:31以一次一次加一个新的值的方式完成sort

Q5 L203 L237 Delete a node/value from LinkedList 2:51:30

删值需要先找到值，重复状态下怎么删值
定位到要删的node
- with head：要删的前提需要知道previous node
  - prev = head, if prev.next.val == target, prev.next =prev.next.next
- if without head, 把下一个篮子里的值存到要删值的篮子里，要删的值就被替代了，把被提取的篮子删掉

5.1 L83 remove duplicate 2:57:21
- from remove duplicate, wil onlyl be value
- 没有箭头连接的node怎么办？
  - garbage collection：不被使用的时候启用了此机制

Q6 L21 Merge two sorted LinkedList/Array 2:59:56

S1: use dummy node, extra linkedlist
S2: 以pre processing的方式找到头节点去做
- 两个list的头节点，谁小谁就是答案的头节点

public ListNode mergeTwoList(ListNode h1, ListNode h2){
    if(h1 == null) return h2;
    if(h2 == null) return h1;
    ListNode head, cur;
    if(h1.val <= h2.val){ //谁小取谁
        head = h1;
        h1 = h1.next
    }else{
        head = h2;
        h2 = h2.next
    }
    cur = head;
    while(h1 != null && h2 != null){
        if(h1.val < h2.bal){
            cur.next = h1;
            h1 = h1.next;
        }else{
            cur.next = h2;
            h2 = h2.next;
        }
        cur = cur.next;
    }
    if ( h1 != null ) cur.next = h1;
    if ( h2 != null ) cur.next = h2;
    return head;
}

第七节 13:41 review L21 S2: iteration

corner case need to be discussed
S3：merge two linkedlist recursion 25:05

public ListNode mergeTwoList(ListNode l1, ListNode l2){
    if(l1 == null) return l2;
    if(l2 == null) return l1;
    
    if(l1.val < l2.val){
        l1.next = mergeTwoList(l1.next, l2); //wall
        return l1; //把小的return上去以便于把更小的接上
    }else{
        l2.next = mergeTwoList(l1, l2.next); //wall
        return l2;
    }
}

Q7 L143 Reorder List 38:37

pair merge demo过程49:16
S1: extra O(n) space:
- reverse the whole linkedlist and pair merge
S2: in place without alter nodes' value
- 找mid然后断开

public ListNode reorderList(ListNode head){
    //corner case
    if(head == null || head.next == null) return head;
    ListNode mid = findMid(head);
    ListNode leftHead = head;
    ListNode rightHead = mid.next
    mid.next = null; 断开
    
    return merge(leftHead, reverse(rightHead));
}

findMid();
reverse();
    
private ListNode merge(ListNode h1, ListNode h2){
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    ListNode l1 = h1, l2 = h2;
    while(l1 != null && l2 != null){
        cur.next = l1;
        l1 = l1.next;
        cur = cur.next;
        cur.next = l2;
        l2 = l2.next;
        cur cur.next;
    }
    // if(h1 != null) cur.next = l1;
    cur.next = l1;
    return dummy.next;
    
}

Q8 L328 Odd Even List 1:00:04

partition 基于什么：
- 基于值
- 基于奇偶位置
S1：两个dummy node为头节点的linkedlist，一个存odd，一个存even，然后merge起来；／／记得尾节点加null
S2：不能使用dummy node：因为是连续的，所以可以直接存

Q9 L86 Partition List 1:13:50

similiar with quick sort; but it is a single linked list, so it can't be read randomly
should be stable
need a current initialize the input head to traverse or iterate the whole list
- two dummy heads

public ListNode partitionList(ListNode head, int value){
    if(head == null || head.next == null) return head;
    ListNode less = new ListNode(0);
    ListNode larger = new ListNode(0);
    ListNode cur = head;
    ListNode curLess = less;
    ListNode curLarger = larger;
    while(cur != null){
        if(cur.val < value){
            curLess.next = cur;
            curLess = curLess.next;
        }else{
            curLarger.next = cur;
            curLarger = curLarger.next;
        }
        cur = cur.next;
    }
    curLarger.next = null; //null pointer exception
    curLess.next = larger.next;
    return less.next;
}

Q10 L369 Plus One Linked List 1:35:47

10.1 L2 Add two Number --> minus 小数

10.2 add two string

Integer所表示的最大数字是 2^31-1 最小是-2^31 range 2^32

PreviousSort Algorithm NextQueue & Stack

Last updated 4 years ago

Was this helpful?