package cn.infobuy.gouqi.demo;
import cn.infobuy.gouqi.util.ListNode;
import cn.infobuy.gouqi.util.TreeNode;
/**
* 关于链表
* @author JohnLiu
*
*/
public class ListSolution {
/**
* 链表反转
* @param head
* @param m
* @param n
* @return
*/
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode current = head;
int count = 0;
ListNode partHead=null;
ListNode partEnd=null;
while(current!=null) {
// 表示当前的节点是第counter个节点
count++;
if(count==m-1) {
partHead=current;
}
if(count==n+1) {
partEnd=current;
}
current = current.next;
}
if(partHead==null) {
return reverseList(head, partEnd);
}else {
ListNode newPartHead = reverseList(partHead.next, partEnd);
partHead.next=newPartHead;
return head;
}
}
/**
* 旋转链表
* 给定一个链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
* @param head
* @param k
* @return
*/
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k <= 0) {
return head;
}
ListNode current = head;
int n = 1;
//O(n)
while (current.next != null) {
n++;
current = current.next;
}
current.next = head;
int count = n - k % n;
ListNode result = null;
for (int i = 0; i < count; i++) {
current = current.next;
}
result = current.next;
current.next = null;
return result;
}
/**
* k个一组翻转链表
* 递归版本
* @param head
* @param k
* @return
*/
public ListNode reverseKGroup1(ListNode head, int k) {
ListNode current_node = head;
int count = 0;
while (current_node != null && count != k) {
current_node = current_node.next;
count++;
}
if (count == k) {
current_node = reverseKGroup(current_node, k);/// 递归的解决子问题
while (count-- > 0) {
ListNode temp = head.next;
head.next = current_node;
current_node = head;
head = temp;
}///最终,该段的所有节点将会截空,head应指向current_node
head = current_node;
}
return head;
}
/**
* k个一组翻转链表
* 迭代版本
* @param head
* @param k
* @return
*/
public ListNode reverseKGroup(ListNode head, int k) {
ListNode finalhead = new ListNode(0);
finalhead.next=head;
ListNode partHead = null;
ListNode partNextHead = head;
ListNode parent = finalhead;
while((partHead=partNextHead)!=null){
// 迭代寻找 partNextHead
int tmpK = k-1;
while((partNextHead=partNextHead.next)!=null&&tmpK>0){
tmpK--;
}
if(tmpK>0){
break;
}
reverseList(parent,partHead,partNextHead);
parent=partHead;
}
return finalhead.next;
}
/**
* 通过三个指针实现整个链表[head,endTarget.pre]的翻转
* head:记录链表的头部
* surplexHead: 记录链表剩余的头部
* next:当前操作的节点
* @param head
* @return
*/
public ListNode reverseList(ListNode head,ListNode end){
ListNode currentNode = null;
ListNode surplexHead = head;
// 一个head指针专门记录处理完成后的head节点
head=end;
while(surplexHead!=end){
currentNode = surplexHead;
surplexHead=currentNode.next;
currentNode.next=head;
head=currentNode;
}
return head;
}
public void reverseList(ListNode parent,ListNode head,ListNode end){
// 当前操作的指针
ListNode currentNode = null;
// 未操作的头指针
ListNode surplexHead = head;
// 已操作好的头指针
head=end;
while(surplexHead!=end){
currentNode = surplexHead;
surplexHead=surplexHead.next;
currentNode.next=head;
head=currentNode;
}
parent.next=head;
}
/**
* 合并两个有序链表为一个有序链表
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null&&l2==null){
return null;
}
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
if(l1.val>l2.val){
l2.next=mergeTwoLists(l1,l2.next);
return l2;
}else{
l1.next=mergeTwoLists(l1.next,l2);
return l1;
}
}
/**
* 合并K个排序链表
* 合并2个会的,那合并k个呢?
*
* @param lists
* @return
*/
public ListNode mergeKLists(ListNode[] lists) {
if (lists==null||lists.length==0){
return null;
}
return mergeLists(lists,0,lists.length-1);
}
/**
* 利用归并排序的思想
* k个列表,每次拆成2堆,然后每堆生成一个排序后的链表,再将两个排序后的链表升为一个链表并返回
* 时间复杂度为 O(lg(K)kn)
* @param lists
* @param left
* @param right
* @return
*/
private ListNode mergeLists(ListNode[] lists, int left, int right) {
int mid = (left+right)/2;
if (left<right){
ListNode l1 = mergeLists(lists, left, mid);
ListNode l2 = mergeLists(lists, mid + 1, right);
return mergeTwoLists(l1,l2);
}
return lists[left]; //如果left==right则直接返回左面的链表
}
/**
* 删除链表的倒数第N个节点
* @param head
* @param n
* @return
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode reachEnd=head;
ListNode reachNth=head;
int depth=n;
// 确保 reachEnd 比 reachNth 快 n步
while(depth>=1){
reachEnd=reachEnd.next;
depth--;
}
ListNode markPreNode = null;
while(reachEnd!=null){
reachEnd=reachEnd.next;
markPreNode=reachNth;
reachNth=reachNth.next;
}
if(head==reachNth){
// 如果head被删除了
return head.next;
}else{
markPreNode.next=reachNth.next;
return head;
}
}
/**
* 两两交换链表中的节点
* 给定 1->2->3->4, 你应该返回 2->1->4->3.
* @param head
* @return
*/
public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode a = new ListNode(0);
a.next=head;
head=a;
while(head.next!=null&&head.next.next!=null){
ListNode nextNode=head.next.next;
ListNode firstNode = head.next;
// swapPairs
firstNode.next=nextNode.next;
head.next=nextNode;
nextNode.next=firstNode;
// 迭代
head=firstNode;
}
return a.next;
}
/**
* 删除排序链表中的重复元素
* @param head
* @return
*/
public ListNode deleteDuplicates(ListNode head) {
ListNode l1 = head;
//验证 head.next 是否要加入
while(head!=null&&head.next!=null){
if(head.next.val==head.val){
head.next=head.next.next;
}else{
head = head.next;
}
}
return l1;
}
/**
* 删除排序链表中的重复元素 II
* @param head
* @return
*/
public ListNode deleteDuplicates2(ListNode head) {
// 标记头节点
ListNode parent = new ListNode(-1);
ListNode certainTail = parent;
// 第一个节点暂定为head
certainTail.next=head;
// 指定目前暂定的节点,考虑是否要加入certainTail链表中
ListNode tmpTail = head;
while(tmpTail!=null&&tmpTail.next!=null) {
if(tmpTail.val!=tmpTail.next.val) {
certainTail.next=tmpTail;
certainTail=tmpTail;
tmpTail=tmpTail.next;
}else {
while(tmpTail.next!=null&&tmpTail.val==tmpTail.next.val) {
tmpTail.next=tmpTail.next.next;
}
tmpTail=tmpTail.next;
certainTail.next=tmpTail;
}
}
return parent.next;
}
/**
* 分隔链表
* 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
* 你应当保留两个分区中每个节点的初始相对位置。
* @param head
* @param x
* @return
*/
public ListNode partition(ListNode head, int x) {
if(head==null) {
return null;
}
ListNode top = head;
ListNode current = null;
// 验证head.next是否满足条件
while(head.next!=null) {
if(head.next.val<x) {
current=head.next;
head.next=head.next.next;
current.next=top;
top=current;
}else {
head = head.next;
}
}
return top;
}
public ListNode partition2(ListNode head, int x) {
ListNode top = new ListNode(0);
top.next=head;
head=top;
ListNode current = null;
ListNode newHead = null;
ListNode newTail = null;
// 验证head.next是否满足条件
while(head.next!=null) {
if(head.next.val<x) {
current=head.next;
head.next=head.next.next;
if(newHead==null) {
newHead = current;
newTail = current;
}else {
newTail.next=current;
newTail = current;
}
}else {
head = head.next;
}
}
if(newHead!=null) {
newTail.next=top.next;
}else {
newHead = top.next;
}
return newHead;
}
/**
* 将有序链表转为二叉树BST
* @param head
* @return
*/
public TreeNode sortedListToBST(ListNode head) {
return sortedListToBST(head,null);
}
public TreeNode sortedListToBST(ListNode head,ListNode end) {
if(head==end) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=end&&fast.next!=end) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode c = new TreeNode(slow.val);
c.left=sortedListToBST(head,slow);
c.right=sortedListToBST(slow.next,end);
return c;
}
}
网友评论