通过编码实现日常关于链表可能会遇到到编程题

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

公众号分类整理了各种资料快去看看吧