Flip the list in groups of K

You are given a linked list, each k nodes in a group of flipped, please return to the flipped list. K is a positive integer whose value is less than or equal to the length of the list. If the total number of nodes is not an integer multiple of k, keep the last remaining nodes in the same order. Example:

To give you this list: 1 - > 2 - > 3 - > when k = 2, 4 - > 5, should return: 4 - > 2 - > 1 - > 3 - > 5 when k = 3, should return: 3 - > 2 - > 1 - > 4 - > 5Copy the code

link

The stack

Analysis of the problem solving

  • Make use of the characteristics of the stack after the implementation of the flip
  • First, calculate the length of the linked list to facilitate subsequent grouping and calculation
  • Create a stack and a linked list of results as temporary storage
  • Groups iterate over the linked list, pushing the values in each group in order, and popping up and adding to the result list after the completion of each group
  • At the end of the loop, the head pointer of the child list that is not in any group is appended to the resulting list
  • Returns the header pointer to the result list
package LT; /* * Created by lizeyu on 2020/9/13 0:55 */ import java.util.Stack; public class ReversedLinkedListByStack { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public ListNode reverseKGroup(ListNode head, int k) { ListNode curr = head; int length = 0; while (head ! = null) { length++; head = head.next; } Stack<Integer> stack = new Stack<>(); ListNode result = new ListNode(0); ListNode dummyNode = result; for (int i = 0; i < length / k; i++) { for (int j = 0; j < k; j++) { stack.push(curr.val); curr = curr.next; } while (! stack.isEmpty()) { result.next = new ListNode(stack.pop()); result = result.next; } } if (curr ! = null) { result.next = curr; } return dummyNode.next; }}Copy the code

** Time complexity: O(N), where N is the length of the list, space complexity: the need for extra space – stack, O(N) **

Iterative method, multi – pointer recording method

  • We’re going to use a function that flips the list
package LT; /* * Created by lizeyu on 2020/9/12 23:08 */ public class ReverseNodesInKGroups { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public ListNode reverseKGroup(ListNode head, int k) { ListNode dummyNode = new ListNode(0); dummyNode.next = head; ListNode pre = dummyNode, end = dummyNode; while (end.next ! = null) { for (int i = 0; i < k; i++) { if (end == null) { break; } end = end.next; } if (end==null){ break; } ListNode next = end.next; ListNode start = pre.next; end.next = null; pre.next = reverseList(start); start.next = next; pre = start; end = pre; } return dummyNode.next; } public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode curr = head; while (curr ! = null) { ListNode temp = curr.next; curr.next = pre; pre = curr; curr = temp; } return pre; }}Copy the code

Circular linked list 2

Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list.

Note: Modification of a given linked list is not allowed.

link

Hash table

Analysis of the problem solving

  • Iterate over all nodes and store a reference (or memory address) to each node in a hashSet. If the current node is null, the proof is that the end of the list has been traversed and there is no loop, and null is returned. If a reference to the current node appears in the hashSet, the current node is returned
package LT; /* * Created by lizeyu on 2020/9/13 16:11 */ import java.util.HashSet; public class LinkedListCycle2BySet { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public ListNode detectCycle(ListNode head) { HashSet<ListNode> hashSet = new HashSet<>(); while (head! =null){ if (hashSet.contains(head)){ return head; } hashSet.add(head); head = head.next; } return null; }}Copy the code

Fast and slow pointer methods

public class Solution { private ListNode getIntersect(ListNode head) { ListNode tortoise = head; ListNode hare = head; while (hare ! = null && hare.next ! = null) { tortoise = tortoise.next; hare = hare.next.next; if (tortoise == hare) { return tortoise; } } return null; } public ListNode detectCycle(ListNode head) { if (head == null) { return null; } ListNode intersect = getIntersect(head); if (intersect == null) { return null; } ListNode ptr1 = head; ListNode ptr2 = intersect; while (ptr1 ! = ptr2) { ptr1 = ptr1.next; ptr2 = ptr2.next; } return ptr1; }}Copy the code

Circular linked list

Make a linked list and determine whether there are rings in the list.

To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list.

link

Hash tables require extra space

Analysis of the problem solving

  • Iterate over all nodes and store a reference (or memory address) to each node in a hashSet. If the current node is null, the proof is that the end of the list is traversed and there is no loop, then false is returned. Returns true if the reference to the current node appears in the hashSet
package LT; /* * Created by lizeyu on 2020/9/13 11:57 */ import java.util.HashSet; public class LinkedListCycle { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public boolean hasCycle(ListNode head) { HashSet<ListNode> hashSet = new HashSet<>(); while (head! =null){ if (hashSet.contains(head)){ return true; } else{ hashSet.add(head); head = head.next; } } return false; }}Copy the code

** Time complexity: O(N), for a list with N elements, we access each element at most once, adding a node to the hash table takes O(1) time **

** Spatial complexity: Depending on the number of elements added to the hash table, up to n elements can be added **

Fast and slow pointer method, no extra space consumption, space complexity can be reduced to O(1)

Analysis of the problem solving

  • Move with two fast and slow hands with different starting points, the slow hands move one step at a time, and the fast hands move two steps at a time
    • If the current list does not have a ring, the fast pointer will encounter a null node, and return false
    • Return true if there is a loop in the current list and the fast pointer must catch up with the slow pointer
    • Think of it as a track race
package LT; /* * Created by lizeyu on 2020/9/13 12:13 */ public class LinkedListCycleBySlowFastPointers { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public boolean hasCycle(ListNode head) { if (head == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow ! = fast) { if (fast == null || fast.next == null || fast.next.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; }}Copy the code

** Space complexity: Only fast and slow Pointers are used, so the space complexity is O(1) **

** Time complexity :O(N) **