Linked List

8 flashcards · Other · by Steven Bui

1. 141. Linked List Cycle Given only the start node of the linked list (head), return true if the linked list has a cycle in it. ex. Input: head = [3, 2, 0, -4] Output: true ---------------------------------------------------------------------------------- public boolean method (ListNode head) { .... } class ListNode { ....int val; ....ListNode next; ....ListNode (int x) { ........val = x; ........next = null; ....} }

   Approach: First, check if the head is null (empty list). Then, create 2 pointers: a slow pointer that moves 1 node at a time, and a fast pointer that moves 2 nodes at a tome. While the fast pointer is not null (it is a node) and the fast pointer's next node is not null either, move slow 1 node forward and fast 2 nodes forward. If slow is equal to fast, return false. Code: public boolean method (ListNode head) { ....if (head == null) { ........return false; ....} ....ListNode slow = head; ....Li…

2. 21. Merge 2 Sorted Lists Given the heads of 2 different linked lists (list1 and list2), combine both of them into one linked list, and return the head of that list. ex. Input: list1 = [1, 2, 4], and list2 = [1, 3, 4] Output: [1, 1, 2, 3, 4, 4] ---------------------------------------------------------------------------------- public ListNode method (ListNode list1, ListNode list2) { .... } class ListNode { ....int val; ....ListNode next; ....ListNode (int x) { ........val = x; ........next = nul…

   Approach: First, create 2 pointers: 1 is a "dummy" node which is the node at index -1 of the returned list, and 1 is a "current" node for adding onto the dummy node. We never move the dummy node, we will only be moving current. While both list1 and list2 are not null (aka until one is null), compare the values at list1 and list2 (these are nodes). If list1 value is smaller, then do 3 things: Set current.next to list1 Move list1 forward to list.next Move current forward to current.next Repeat th…

3. 2. Add Two Numbers You are given the heads of 2 different linked lists (l1 and l2), both of which represent a number backwards (ex. 2 -> 4 -> 3 is the number 342). Add the 2 numbers together, and return the head of that linked list. Each node only has 1 digit, and no nodes have leading zeroes. ex. Input: l1 = [2, 4, 3], and l2 = [5, 6, 4] Output: 342 + 465 = 807 ---------------------------------------------------------------------------------- public ListNode method (ListNode l1, ListNode l2) {…

   Approach: First, create 2 pointers: 1 is a "dummy" node which is the node at index -1 of the returned list, and 1 is a "current" node for adding onto the dummy node. We never move the dummy node, we will only be moving current. Also, create a variable called "carry" for carrying over a number to add. As long as at least one of the linked lists is not null, set a sum variable to carry first. Then, if l1 is not yet null, add its value to sum and move l1 forward. Do the same for l2. Update carry,…

4. 206. Reverse Linked List Given the head of a linked list, return the reversed linked list. ex. Input: head = [1, 2, 3, 4, 5] Output: [5, 4, 3, 2, 1] ---------------------------------------------------------------------------------- public ListNode method (ListNode head) { .... } class ListNode { ....int val; ....ListNode next; ....ListNode (int x) { ........val = x; ........next = null; ....} }

   Approach: First, create 2 pointers: current points to the head and deals with the current node. The pointer prev will point to null right now, but you will add the current node to prev as you traverse the given list. In a while-loop while current is not null, you're going to do 4 steps: Initialize a new node called next, which points to current.next. You need to store next because you're about to change what current.next points to. Set current.next to prev. prev represents the start (index 0) o…

5. 19. Remove the Nth-to-Last Node Given the head of a linked list, remove the nth node from the end of the linked list and return the head. n starts at 1, so if n is 1, you remove the last node. ex. Input: head = [1, 2, 3, 4, 5], and n = 2 Output: [1, 2, 3, 5] ---------------------------------------------------------------------------------- public ListNode method (ListNode head, int n) { .... }

   Approach: Create 3 pointers: 1 is a "dummy" node which is the node at index -1 of the returned list, which is needed to return head. Set dummy.next to head. 1 is called behind and currently points to dummy, and it represents the node that stays n nodes behind the ahead node (also pointing at dummy). Then, move ahead n spaces ahead of behind while the index of the for-loop is LESS THAN OR EQUAL TO n. Then, move both ahead and behind until ahead is null. At this point, behind will be right behind…

6. 328. Odd-Index Even-Index List Given the head of a linked list, rearrange the list so that all of the nodes with odd indices are at the beginning of the list in the same order, and all of the nodes with odd indices are at the end of the list in the same order. The first node is considered ODD, so it should stay at the beginning. ex. Input: head = [2, 1, 3, 5, 6, 4, 7] Output: [2, 3, 6, 7, 1, 5, 4] ---------------------------------------------------------------------------------- public ListNode…

   Approach: First, create 2 pointers: odd is the head of a new linked list that points to head and represents the odd indices, and even is a new linked list that points to head.next and represents the even indices. Also, create another pointer called connect which points to even (you won't use this until the end to connect the 2 linked lists). In a while-loop while even is not null and even.next is not null, make odd's next node point to the next odd-indexed node, and make odd move to that node.…

7. 61. Rotate Linked List Given the head of a linked list, rotate the list by k spaces. In other words, the first node should be k units to the right, etc. Nodes at the end of the linked list would be at the beginning of the list. ex. Input: head = [1, 2, 3, 4, 5], and k = 2 Output: [4, 5, 1, 2, 3] ---------------------------------------------------------------------------------- public ListNode method (ListNode head, int k) { .... }

   Approach: The strategy is basically making the entire list circular by making the last node's next pointer point to the head node. From there, you see find out what the last node of the returned list would be and then save its next pointer (the new "head") and then set that last node's next pointer point to null, making the list no longer circular. First, traverse the list to get to the last node AND get the length of the list. Set the last node's next to head, making the list circular. Then, f…

8. 2095. Skip the Middle Node Given the head of a linked list, skip the node in the middle and return the head of the list. If there is an even number of nodes, remove the node rounding up. ex. Input: head = [1, 2, 3, 4] Output: [1, 2, 4] ---------------------------------------------------------------------------------- public ListNode method (ListNode head) { .... }

   Approach: First, create a dummy node and set its next value to the head (so you can return dummy.next at the end). Create 2 ListNodes: a slow pointer that moves 1 at a time, and a fast pointer that moves 2 at a time. Initialize slow to dummy and fast to head (since you skip the upper node). While fast is not null and fast.next is not null, move slow 1 at a time and fast 2 at a time. When you break out of the loop, make slow skip the middle node, and return dummy.next. Code: public ListNode meth…