As for the data structure, this time I finally made up my mind to make a summary. Before that, all kinds of scattered summaries were not systematic. Here is a summary of some basic data structures. University has studied the theory of data structure, but it has not been fully implemented with code.
Definition of linked list and node
Definition of nodes
/** * autor:liman * comment: Nodes corresponding to linked list */ public class ListNode { public int value; public ListNode next; public ListNode(int value) { this.value = value; } }
This is a very simple definition. There's nothing to say. It's easy to learn data structure
Definition of linked list
The definition of linked list is to encapsulate some basic operations on the basis of nodes. Some operations of insertion and deletion are good. Here, the code is posted directly
package com.learn.LinkList; /** * autor:liman * comment: */ public class SelfLinkedList { /** * Insertion of head node * @param head * @param newHead */ public static void headInsert(ListNode head,ListNode newHead){ ListNode old = head; head = newHead; head.next = old; } /** * Insertion without nodes * @param tail * @param newTail */ public static void tailInsert(ListNode tail,ListNode newTail){ ListNode old = tail; tail = newTail; newTail.next = null; old.next = tail; } /** * Traversing linked list * @param head */ public static void traverse(ListNode head){ while(head!=null){ System.out.print(head.value+" "); head = head.next; } System.out.println(); } /** * Find node, return node index * @param head * @return */ public static int findNode(ListNode head,int value){ int index = -1; int count = 0; while(head!=null){ if(head.value == value){ index = count; return index; } count++; head = head.next; } return index; } /** * Insert the s node after the pre node * @param pre * @param s */ public static void insertAfterNode(ListNode pre,ListNode s){ ListNode pAfter = pre.next; pre.next = s; s.next = pAfter; } /** * Delete node s, copy the next of s to s, and then delete the subsequent nodes of S * @param head * @param s */ public static void deleteNode(ListNode head,ListNode s){ if(s!=null && s.next!=null){//This does not include deleting the tail node ListNode sNext = s.next; s.value = sNext.value; //Delete next node of s s.next = sNext.next; sNext=null; } //If the tail node is deleted if(s.next==null){ //Traversal search and hit precursor while(head!=null){ if(head.next!=null && head.next == s){ head.next=null; break; } head=head.next; } } } }
The operation of deleting a node is troublesome to find the precursor node. Here you steal a lazy one, copy the successor node to the current node directly, and then delete the current node.
Some practical operations
Chain flip
Idea: use three pointers to walk the chain in turn, turn the two pointers behind the team at each step.
/** * Flip list, time complexity O(n), space complexity O(1) * * @param head */ public static ListNode reverseList(ListNode head) { ListNode preNode = null; ListNode afterNode = null; while (head != null){ afterNode = head.next; head.next=preNode; preNode = head; head = afterNode; } return preNode; }
Get intermediate node
Idea: take the middle node. If the chain length is odd, take the middle node directly. If it is an even number, take the former one in the middle.
Define two pointers. The fast pointer takes two steps at a time and the slow pointer takes one step at a time. When the fast pointer reaches the end, the slow pointer is the middle node.
/* * @param head * @return */ public static ListNode getMiddleNode(ListNode head){ if(head==null){ return head; } ListNode fastNode = head; ListNode slowNode = head; while(fastNode.next!=null && fastNode.next.next!=null){ slowNode = slowNode.next; fastNode = fastNode.next.next; } return slowNode; }
Merge two ordered lists
There are several ways to implement this, one is recursion, the other is non recursion.
Recursive implementation
/** * Merge ordered list recursively * * @param head01 * @param head02 * @return */ public static ListNode mergeTwoListRecursive(ListNode head01, ListNode head02) { //Recursive export if (head01 == null && head02 == null) { return null; } if (head01 == null) { return head02; } if (head02 == null) { return head01; } ListNode head = null;//Combined head node if (head01.value > head02.value) { head = head02; head.next = mergeTwoListRecursive(head01, head02.next); } else { head = head01; head.next = mergeTwoListRecursive(head01.next, head02); } return head; }
Non recursive implementation
/** * Merge two linked lists non recursively. * * @param head01 * @param head02 * @return */ public static ListNode mergeTwoList(ListNode head01, ListNode head02) { if (head01 == null || head02 == null) { return head01 != null ? head01 : head02; } ListNode head = head01.value <= head02.value ? head01 : head02; ListNode cur1 = head == head01 ? head01 : head02; ListNode cur2 = head == head01 ? head02 : head01; ListNode pre = null; ListNode next = null; while (cur1 != null && cur2 != null) { if (cur1.value <= cur2.value) {//Merge cur1 into the target linked list pre = cur1; cur1 = cur1.next; } else {//Merge cur2 into the target linked list next = cur2.next; pre.next = cur2; cur2.next = cur1; pre = cur2; cur2 = next; } } pre.next = cur1 == null ? cur2 : cur1; return head; }
Some interview questions
Odd ascending, even descending
A linked list, odd bits in ascending order, even bits in descending order, to sort the linked list. For example: 1 - > 8 - > 3 - > 6 - > 5 - > 4 - > 7 - > 2 - > 9, it needs to be sorted
Ideas: 1. Split it into two linked lists according to odd and even digits. 2. The linked list of dual digits is flipped. 3. Merge sort
The complete implementation is posted here
/** * autor:liman * createtime:2020/2/4 * A linked list, odd digit ascending, even digit descending, to sort the linked list */ public class InterviewTitleOne { /** * There are three steps: * 1,Split by odd and even digits * 2,Dual digit flip * 3,Merge sort */ public static void main(String[] args) { ListNode node01 = new ListNode(1); ListNode node02 = new ListNode(8); ListNode node03 = new ListNode(3); ListNode node04 = new ListNode(6); ListNode node05 = new ListNode(5); ListNode node06 = new ListNode(4); ListNode node07 = new ListNode(7); ListNode node08 = new ListNode(2); ListNode node09 = new ListNode(9); node01.next = node02; node02.next = node03; node03.next = node04; node04.next = node05; node05.next = node06; node06.next = node07; node07.next = node08; node08.next = node09; ListNode[] listNodes = getList(node01); ListNode head01 = listNodes[0]; ListNode head02 = listNodes[1]; //Flip even bit list head02=reverseList(head02); ListNode result = mergetList(head01,head02); SelfLinkedList.traverse(result); } /** * Split linked list by parity * * @param head * @return */ public static ListNode[] getList(ListNode head) { ListNode head01 = null; ListNode head02 = null; ListNode cur01 = null; ListNode cur02 = null; int count = 1; while (head != null) { if (count % 2 == 1) {//Odd node if(cur01!=null){ cur01.next = head; cur01 = cur01.next; }else{ cur01 = head; head01 = cur01; } }else{ if(cur02!=null){ cur02.next = head; cur02 = cur02.next; }else{ cur02 = head; head02 = cur02; } } head = head.next; count++; } cur01.next = null; cur02.next = null; ListNode[] nodes = new ListNode[]{head01,head02}; return nodes; } /** * Flip list * @param head * @return */ public static ListNode reverseList(ListNode head){ ListNode pre = null; ListNode next = null; while(head!=null){ next = head.next; head.next = pre; pre = head; head = next; } return pre; } /** * Merge two linked lists (recursive implementation) * @param head01 * @param head02 * @return */ public static ListNode mergetList(ListNode head01,ListNode head02){ if(head01 == null && head02 ==null){ return null; } if(head01==null){ return head02; } if(head02 == null){ return head01; } ListNode head = null; if(head01.value>head02.value){ head=head02; head.next = mergetList(head01,head02.next); }else{ head = head01; head.next = mergetList(head01.next,head02); } return head; } }
The flipping and merging operations have been introduced before, and will not be discussed here. The splitting operation is worthy of attention here.
To realize the merging and sorting of linked list
Merge sort should be the best choice of chain list sort, which ensures that the best and the best time complexity are nlogn, and the space complexity of merge sort in array is O(n), which also becomes O(1) in chain list.
Ideas: 1. Divide the array (linked list) to be sorted into two parts. 2. Recursively merge and sort the left part. 3. Recursively merge and sort the right part. 4. Merge and sort the two parts to get the result.
package com.learn.LinkList; /** * autor:liman * createtime:2020/2/4 */ public class InterviewTitleTwo { public static void main(String[] args) { ListNode node01 = new ListNode(1); ListNode node02 = new ListNode(8); ListNode node03 = new ListNode(3); ListNode node04 = new ListNode(6); ListNode node05 = new ListNode(5); ListNode node06 = new ListNode(4); ListNode node07 = new ListNode(7); ListNode node08 = new ListNode(2); ListNode node09 = new ListNode(9); node01.next = node02; node02.next = node03; node03.next = node04; node04.next = node05; node05.next = node06; node06.next = node07; node07.next = node08; node08.next = node09; ListNode sortedList = sortList(node01); SelfLinkedList.traverse(sortedList); } /** * Merging and sorting algorithm of linked list * * @param head * @return */ public static ListNode sortList(ListNode head) { if (head == null || head.next==null) {//0 or 1 elements, return directly without sorting return head; } ListNode middleNode = getMiddleNode(head); ListNode rightFirst = middleNode.next; middleNode.next=null;//Split into two linked lists; ListNode node=merge(sortList(head),sortList(rightFirst)); return node; } /** * Get intermediate node * * @param head * @return */ public static ListNode getMiddleNode(ListNode head) { if (head == null) { return head; } ListNode fastNode = head; ListNode slowNode = head; while (fastNode.next != null && fastNode.next.next != null) { slowNode = slowNode.next; fastNode = fastNode.next.next; } return slowNode; } /** * Merge two linked lists in non recursive order * * @param head01 * @param head02 * @return */ public static ListNode merge(ListNode head01, ListNode head02) { if (head01 == null || head02 == null) { return head01 != null ? head01 : head02; } ListNode head = head01.value <= head02.value ? head01 : head02; ListNode cur1 = head == head01 ? head01 : head02; ListNode cur2 = head == head01 ? head02 : head01; ListNode pre = null; ListNode next = null; while (cur1 != null && cur2 != null) { if (cur1.value <= cur2.value) { pre = cur1; cur1 = cur1.next; } else { next = cur2.next; pre.next = cur2; cur2.next = cur1; pre = cur2; cur2 = next; } } pre.next = cur1 == null ? cur2 : cur1; return head; } }
Conclusion:
Summary of some basic operations.
