通过编码实现日常关于链表可能会遇到到编程题
1 两个链表是各自自增的,要求合拼之后的链表满足单调不递减
/**
* 两个递增的单链表合并保持单调递增
*
* 递归求解
* @param firstNode
* @param secondNode
* @return
*/
public Node mergeNode(Node firstNode,Node secondNode){
if (firstNode==null)return secondNode;
if (secondNode==null)return firstNode;
Node mergeNode = null;
if (firstNode.data<secondNode.data){
mergeNode = firstNode;
mergeNode.next = mergeNode(firstNode.next,secondNode);
}
else {
mergeNode = secondNode;
mergeNode.next = mergeNode(firstNode,secondNode.next);
}
return mergeNode;
}
2 单链表排序
/**
* 单链表排序
* 归并排序
*/
public Node sortNode(Node head){
if(head == null|| head.next == null){
return head;
}
Node mid = middleNode(head);
Node right = sortNode(mid.next);
mid.next = null;
Node left = sortNode(head);
return merge(left, right);
}
/**
* 合拼排好序的子链表
* @param n1
* @param n2
* @return
*/
private Node merge(Node n1,Node n2){
Node dummy = new Node(0);
Node node = dummy;
while (n1!=null&&n2!=null) {
if(n1.data<n2.data){
node.next = n1;
n1 = n1.next;
}else{
node.next = n2;
n2 = n2.next;
}
node = node.next;
}
if(n1!=null){
node.next = n1;
}else{
node.next = n2;
}
return dummy.next;
}
/**
* 寻找链表中间值
* @param head
* @return
*/
private Node middleNode(Node head){
Node slow = head;
Node fast = head.next;
while(fast!=null&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
3 单链表整体反转
/**
* 递归方式-进行反转
* @param node
* @return
*/
private Node reverseNodeByDG(Node head){
if(head.next == null){
return head;
}
Node reverseNode = reverseNodeByDG(head.next);
head.next.next = head;
head.next = null;
return reverseNode;
}
/**
* 遍历方式-进行反转
* @param node
* @return
*/
private Node reverseNodeByBL(Node node){
Node prev = null;
while(node!=null){
Node tmp = node.next;
node.next = prev;
prev = node;
node = tmp;
}
return prev;
}
4 单链表从n到m位置的反转
/**
* 翻转链表的n到m之间的节点
*/
Node reverseFromNTOM(Node head,int m,int n){
if(m>=n||head == null){
return head;
}
Node dummy = new Node(0);
dummy.next = head;
head = dummy;
for(int i = 1;i<m;i ){
if(head == null){
return null;
}
head = head.next;
}
Node pmNode = head;
Node mNode = head.next;
Node nNode = mNode;
Node pnNode = mNode.next;
for(int i = m;i<n;i ){
if(pnNode == null){
return null;
}
Node tmp = pnNode.next;
pnNode.next = nNode;
nNode = pnNode;
pnNode = tmp;
}
pmNode.next = nNode;
mNode.next = pnNode;
return dummy.next;
}
5 单链表根据指定值进行分割
/**
* 单链表分区
* 小于x的结点排在大于或等于x的结点之前
*/
public Node nodePartition(Node head,int x){
if(head == null){
return null;
}
Node left = new Node(0);
Node right = new Node(0);
Node leftNode = left;
Node rightNode = right;
while(head!=null){
if(head.data<x){
left.next = head;
left = head;
}else{
right.next = head;
right = head;
}
head = head.next;
}
left.next = rightNode.next;
right.next = null;
return leftNode.next;
}
公众号分类整理了各种资料快去看看吧
