# Data structure -- basic operation of linked list

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

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:
*/

/**
*/
}

/**
* 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;
}

/**
*/
}
System.out.println();
}

/**
* Find node, return node index
* @return
*/
public static int findNode(ListNode head,int value){
int index = -1;
int count = 0;
index = count;
return index;
}
count++;
}
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 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
break;
}
}
}
}

}

```

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)
*
*/
public static ListNode reverseList(ListNode head) {
ListNode preNode = null;
ListNode afterNode = null;
}
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.

```    /*
* @return
*/
}
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
*
* @return
*/
//Recursive export
return null;
}
}
}

} else {
}
}
```

### Non recursive implementation

```    /**
* Merge two linked lists non recursively.
*
* @return
*/
}

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;
}
```

# 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);
//Flip even bit list

}

/**
* Split linked list by parity
*
* @return
*/
public static ListNode[] getList(ListNode head) {

ListNode cur01 = null;
ListNode cur02 = null;
int count = 1;
if (count % 2 == 1) {//Odd node
if(cur01!=null){
cur01 = cur01.next;
}else{
}
}else{
if(cur02!=null){
cur02 = cur02.next;
}else{
}
}
count++;
}
cur01.next = null;
cur02.next = null;
return nodes;
}

/**
* Flip list
* @return
*/
ListNode pre = null;
ListNode next = null;
}
return pre;
}

/**
* Merge two linked lists (recursive implementation)
* @return
*/
return null;
}
}
}
}else{
}
}

}

```

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);
}

/**
* Merging and sorting algorithm of linked list
*
* @return
*/
public static ListNode sortList(ListNode head) {
if (head == null || head.next==null) {//0 or 1 elements, return directly without sorting
}
ListNode rightFirst = middleNode.next;
return node;
}

/**
* Get intermediate node
*
* @return
*/
public static ListNode getMiddleNode(ListNode 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
*
* @return
*/
}

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;  