Linked list related interview questions

Linked list speed pointer

1） Input chain header node , Odd length returns the midpoint , Even length returns the upper midpoint
2） Input chain header node , Odd length returns the midpoint , Even length returns the lower midpoint
3） Input chain header node , Odd length returns the one before the midpoint , Even length returns the one before the upper midpoint
4） Input chain header node , Odd length returns the one before the midpoint , Even length returns the one before the lower midpoint
hard coding problem ：

public static class Node {
    
		public int value;
		public Node next;

		public Node(int v) {
    
			value = v;
		}
	}

	// head  head 
	public static Node midOrUpMidNode(Node head) {
    
		if (head == null || head.next == null || head.next.next == null) {
    
			return head;
		}
		//  The list has 3 Points or more 
		Node slow = head.next;
		Node fast = head.next.next;
		while (fast.next != null && fast.next.next != null) {
    
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	public static Node midOrDownMidNode(Node head) {
    
		if (head == null || head.next == null) {
    
			return head;
		}
		Node slow = head.next;
		Node fast = head.next;
		while (fast.next != null && fast.next.next != null) {
    
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	public static Node midOrUpMidPreNode(Node head) {
    
		if (head == null || head.next == null || head.next.next == null) {
    
			return null;
		}
		Node slow = head;
		Node fast = head.next.next;
		while (fast.next != null && fast.next.next != null) {
    
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	public static Node midOrDownMidPreNode(Node head) {
    
		if (head == null || head.next == null) {
    
			return null;
		}
		if (head.next.next == null) {
    
			return head;
		}
		Node slow = head;
		Node fast = head.next;
		while (fast.next != null && fast.next.next != null) {
    
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

Given the header node of a single chain table head, Please judge whether the linked list is palindrome structure .

Ideas ：
1： First, traverse the single linked list , Then put each element on the stack , Then traverse the single linked list again , Compare the top elements of the stack and the linked list elements in turn , If equal, the stack pops up the current element , And the linked list moves to the next node , If a linked list element is not equal to the current stack top element
Then return directly , Not a linked list of palindromes .
2、 If the linked list with odd length returns the midpoint , If it is an even length linked list, return to the upper midpoint , Then reverse the elements after the midpoint , There will be a L Value and R value .
Such as ：
1 2 2 1 It's even , Returning to the upper midpoint is the first one 2 Where it is , The first one at this time 2 Of next Point to null, Let the second 2 Of next Point to the first one 2, the second 1 Of next Point to the second 2, There is a header node , And a tail node , Then the head node and the tail node are compared in turn , If they are equal, they all move , If there is any inequality, return false, If at the end of the move, either party is null Is a palindrome structure

public static class Node {
    
		public int value;
		public Node next;

		public Node(int data) {
    
			this.value = data;
		}
	}

	// need n extra space
	public static boolean isPalindrome1(Node head) {
    
		Stack<Node> stack = new Stack<>();
		Node cur = head;
		while (cur != null) {
    
			stack.push(cur);
			cur = cur.next;
		}
		while (head != null) {
    
			if (head.value != stack.pop().value) {
    
				return false;
			}
			head = head.next;
		}
		return true;
	}

	// need n/2 extra space
	public static boolean isPalindrome2(Node head) {
    
		if (head == null || head.next == null) {
    
			return true;
		}
		Node right = head.next;
		Node cur = head;
		while (cur.next != null && cur.next.next != null) {
    
			right = right.next;
			cur = cur.next.next;
		}
		Stack<Node> stack = new Stack<Node>();
		while (right != null) {
    
			stack.push(right);
			right = right.next;
		}
		while (!stack.isEmpty()) {
    
			if (head.value != stack.pop().value) {
    
				return false;
			}
			head = head.next;
		}
		return true;
	}

	// need O(1) extra space
	public static boolean isPalindrome3(Node head) {
    
		if (head == null || head.next == null) {
    
			return true;
		}
		Node n1 = head;
		Node n2 = head;
		while (n2.next != null && n2.next.next != null) {
     // find mid node
			n1 = n1.next; // n1 -> mid
			n2 = n2.next.next; // n2 -> end
		}
		
		// n1  Midpoint 
		n2 = n1.next; // n2 -> right part first node
		n1.next = null; // mid.next -> null
		Node n3 = null;
		while (n2 != null) {
     // right part convert
			n3 = n2.next; // n3 -> save next node
			n2.next = n1; // next of right node convert
			n1 = n2; // n1 move
			n2 = n3; // n2 move
		}
		n3 = n1; // n3 -> save last node
		n2 = head;// n2 -> left first node
		boolean res = true;
		while (n1 != null && n2 != null) {
     // check palindrome
			if (n1.value != n2.value) {
    
				res = false;
				break;
			}
			n1 = n1.next; // left to mid
			n2 = n2.next; // right to mid
		}
		n1 = n3.next;
		n3.next = null;
		while (n1 != null) {
     // recover list
			n2 = n1.next;
			n1.next = n3;
			n3 = n1;
			n1 = n2;
		}
		return res;
	}

Divide one-way linked list into left small ones according to a certain value 、 Intermediate equality 、 Large form on the right

Given head And a partition value V
1） Put the list in the array , Do... On arrays partition（ Pen trial ）
2） Divide into small 、 in 、 Three parts , And string the parts together （ For interview ）
Ideas ：
2 Methods are divided into 3 The part is mainly divided into smaller than the region head and smaller than the region tail , Equal to the region head and tail , Larger than area head and tail
The linked list is as follows ：
3 5 2 6 1 3 3 7 0 V = 3
Less than area
3、 Head and tail point 2
5、2->1
9、2->1->0
Equal area
1、 Head and tail pointing 3
6、3->3
7、3->3->3

Greater than area
2、 Head and tail point 5
4、5->6
8、5->6->7
After the adjustment, let the small tail point to the equal head , Wait for the tail to point to the big head 【 notes ： At this time, maintaining the tail node larger than the area is a guarantee
Get a stability of the final result 】

public static class Node {
    
		public int value;
		public Node next;

		public Node(int data) {
    
			this.value = data;
		}
	}

	public static Node listPartition1(Node head, int pivot) {
    
		if (head == null) {
    
			return head;
		}
		Node cur = head;
		int i = 0;
		while (cur != null) {
    
			i++;
			cur = cur.next;
		}
		Node[] nodeArr = new Node[i];
		i = 0;
		cur = head;
		for (i = 0; i != nodeArr.length; i++) {
    
			nodeArr[i] = cur;
			cur = cur.next;
		}
		arrPartition(nodeArr, pivot);
		for (i = 1; i != nodeArr.length; i++) {
    
			nodeArr[i - 1].next = nodeArr[i];
		}
		nodeArr[i - 1].next = null;
		return nodeArr[0];
	}

	public static void arrPartition(Node[] nodeArr, int pivot) {
    
		int small = -1;
		int big = nodeArr.length;
		int index = 0;
		while (index != big) {
    
			if (nodeArr[index].value < pivot) {
    
				swap(nodeArr, ++small, index++);
			} else if (nodeArr[index].value == pivot) {
    
				index++;
			} else {
    
				swap(nodeArr, --big, index);
			}
		}
	}

	public static void swap(Node[] nodeArr, int a, int b) {
    
		Node tmp = nodeArr[a];
		nodeArr[a] = nodeArr[b];
		nodeArr[b] = tmp;
	}

	public static Node listPartition2(Node head, int pivot) {
    
		Node sH = null; // small head
		Node sT = null; // small tail
		Node eH = null; // equal head
		Node eT = null; // equal tail
		Node mH = null; // big head
		Node mT = null; // big tail
		Node next = null; // save next node
		// every node distributed to three lists
		while (head != null) {
    
			// First record next Location 
			next = head.next;
			// And then next The pointer is disconnected 
			head.next = null;
			if (head.value < pivot) {
    
				if (sH == null) {
    
					sH = head;
					sT = head;
				} else {
    
					// The current position of the small tail connection 
					sT.next = head;
					// Move Xiao Wei's pointer to the current value , Let the current value become the tail 
					sT = head;
					// The same is true for other areas below 
				}
			} else if (head.value == pivot) {
    
				if (eH == null) {
    
					eH = head;
					eT = head;
				} else {
    
					eT.next = head;
					eT = head;
				}
			} else {
    
				if (mH == null) {
    
					mH = head;
					mT = head;
				} else {
    
					mT.next = head;
					mT = head;
				}
			}
			head = next;
		}
		//  Tail smaller than area , Even equals the head of the region , Equal to the tail of the region and greater than the head of the region 
		if (sT != null) {
     //  If there is an area smaller than 
			sT.next = eH;
			eT = eT == null ? sT : eT; //  next step , Who's going to connect the head larger than the area , Become who you are eT
		}
		//  next step , It must be necessary to use eT  Pick it up   Larger than the head of the area 
		//  There is an area equal to ,eT ->  Equal to the tail node of the region 
		//  None equals region ,eT ->  Less than the tail node of the region 
		// eT  Try not to empty the tail node 
		if (eT != null) {
     //  If it is less than and equal to the area , Not at all 
			eT.next = mH;
		}
		return sH != null ? sH : (eH != null ? eH : mH);
	}

Copy list with random pointer

Described below class Node { int value; Node next; Node rand; Node(int val) { value = val; } }
rand A pointer is a new pointer in the node structure of a single linked list ,rand May point to any node in the list , It may also point to null. Given a by Node Head node of acyclic single chain table composed of node type head, Please implement a function to copy the linked list , And return the head node of the copied new linked list . 【 requirement 】 Time complexity O(N), Extra space complexity O(1)

Ideas ：
1、 Container method , Create a sheet map,key It's an old node ,value Is a new node , First traverse
next The pointer , Create a new node （ At this time, the new linked list has no connection information ）, And then go through the list , from map Take out the new node , Then he will be revalued next The pointer points to the newly established node and random The pointer points to the newly established node （ from Map Take out the new node as the node to establish the connection ）【 Of course, the additional space complexity of this method is O(N)】.
2、 Direct linked list to get ：
I don't care random The pointer , Instead, the cloned nodes are embedded in the linked list
First ：

Insert the cloned node in the middle ：

And then go through it again , Traverse two nodes at a time .
First traverse to 1 node , its random Pointer to 3, meanwhile 3 Of next The pointer points to 3 Clone node for , Then I can let 1‘ Of random Pointer to 3’ 了

In this way, a mapping relationship is made structurally , So the old linked list hasn't moved , The new list points to the same as the old list , It's just
It's cloned .

public static class Node {
    
		int val;
		Node next;
		Node random;

		public Node(int val) {
    
			this.val = val;
			this.next = null;
			this.random = null;
		}
	}

	public static Node copyRandomList1(Node head) {
    
		// key  Old node 
		// value  New node 
		HashMap<Node, Node> map = new HashMap<Node, Node>();
		Node cur = head;
		while (cur != null) {
    
			map.put(cur, new Node(cur.val));
			cur = cur.next;
		}
		cur = head;
		while (cur != null) {
    
			// cur  The old 
			// map.get(cur)  new 
			//  new .next -> cur.next Clone node found 
			map.get(cur).next = map.get(cur.next);
			map.get(cur).random = map.get(cur.random);
			cur = cur.next;
		}
		return map.get(head);
	}

	public static Node copyRandomList2(Node head) {
    
		if (head == null) {
    
			return null;
		}
		Node cur = head;
		Node next = null;
		// 1 -> 2 -> 3 -> null
		// 1 -> 1' -> 2 -> 2' -> 3 -> 3'
		while (cur != null) {
    
			next = cur.next;
			cur.next = new Node(cur.val);
			cur.next.next = next;
			cur = next;
		}
		cur = head;
		Node copy = null;
		// 1 1' 2 2' 3 3'
		//  Set it in turn  1' 2' 3' random The pointer 
		while (cur != null) {
    
			next = cur.next.next;
			copy = cur.next;
			copy.random = cur.random != null ? cur.random.next : null;
			cur = next;
		}
		Node res = head.next;
		cur = head;
		//  The old   new   Mixed in with ,next In the direction of ,random correct 
		// next In the direction of , Separate the old and new linked lists 
		while (cur != null) {
    
			next = cur.next.next;
			copy = cur.next;
			cur.next = next;
			copy.next = next != null ? next.next : null;
			cur = next;
		}
		return res;
	}