由于涉及到Floyd判环算法，故先简单阐述一下Floyd判环算法原理。
Floyd判环算法
算法原理：设置两个指针同时从头结点向后访问（当两指针后继不为null），不过两指针的访问速度不一致，第一个指针每次后移一个元素，第二个指针每次后移两个元素。若链表成环，则两指针在某一时刻必然相遇，否则不相遇
计算环长度：
当指针相遇时，保持其中一个指针不动，另一个指针向后访问，每次后移一个单位，当两指针再次相遇时，该指针移动的单位即为环的长度
计算环起始节点：
第一次相遇后，慢指针从头结点向后访问，快指针从相遇点同时向后访问，不过两者的移动速度都为1，当两者再次相遇时，该相遇的节点即为环的起始节点，分析如下：
如下图所示，假设h为链表头结点，p为两指针第一次相遇节点，m为头结点到起始节点走过的路程（经过的节点个数），n为环起始节点到p的路程，则对于第一次相遇有：
慢指针走过的路程：s=m+n+aC
快指针走过的路程：2s=m+n+bC
a，b分别表示两指针相遇前第一次经过p点后绕环的圈数，C表示环的长度，由于快指针的速度是慢指针的两倍，时间一样，故快指针走过的路程是慢指针的两倍。
两式相减有s=(b-a)C=m+n+a*C
故m+n恰为环长度的整数倍
慢指针从头结点到起始节点走了m，由于同时同速度快指针也走了m，而移动前快指针距起始节点距离为n，m+n恰为环长度的整数倍，故快指针移动m后也到了起始节点，即此时相遇点为起始节点
1.寻找链表的第n个节点
/**
* 时间复杂度为O(n),空间复杂度为O(1)
* @param head
* @param kth
* @return
*/
public static SNode getKthNode(SNode head,int kth){
SNode temNode=head,kthNode=null;
for(int count=1;count<kth;count++) {
if(temNode!=null)
temNode=temNode.getNext();
}
while(temNode!=null) {
if(kthNode==null)
kthNode=head;
else
kthNode=kthNode.getNext();
temNode=temNode.getNext();
}
if(kthNode!=null)
return kthNode;
return null;
}
2.1判断链表是否以null结尾,是否包含环
/**
* 时间复杂度为O(n),空间复杂度为O(1)
* @param head
* @return
*/
public static boolean doesLinkedListContainsLoop(SNode head) {
if(head==null)
return false;
SNode fastNode=head,slowNode=head;
while(fastNode.getNext()!=null&&fastNode.getNext().getNext()!=null) {
slowNode=slowNode.getNext();
fastNode=fastNode.getNext().getNext();
if(fastNode==slowNode)
return true;
}
return false;
}
2.2判断给定的链表是否以null结束。如果链表中存在环，找到环的起始节点
/**
* @param head
* @return
*/
public static SNode findBeginOfLoop(SNode head) {
SNode slowNode=head,fastNode=head;
boolean loopExists=false;
if(head==null)
return null;
while(fastNode.getNext()!=null&&fastNode.getNext().getNext()!=null) {
slowNode=slowNode.getNext();
fastNode=fastNode.getNext().getNext();
if(slowNode==fastNode) {
loopExists=true;
break;
}
}
if(loopExists) { //环存在
slowNode=head;
while(slowNode!=fastNode) {
slowNode=slowNode.getNext();
fastNode=fastNode.getNext();
}
return slowNode; //返回环开始节点
}
return null; //环不存在
}
2.3判断链表是否存在环，若存在，则返回环的长度，否则返回0
/**
* @param head
* @return
*/
public static int findLoopLength(SNode head) {
SNode slowNode=head,fastNode=head;
boolean loopExists=false;
int counter=0;
if(head==null)
return 0;
while(fastNode.getNext()!=null&&fastNode.getNext().getNext()!=null) {
slowNode=slowNode.getNext();
counter++;
fastNode=fastNode.getNext().getNext();
if(slowNode==fastNode) {
loopExists=true;
break;
}
}
if(loopExists) {
fastNode=fastNode.getNext();
while(fastNode!=slowNode) {
fastNode=fastNode.getNext();
counter++;
}
return counter;
}
return 0;
}
3.将一个循环链表变成两个循环链表
/**
* @param head
* @param head1
* @param head2
*/
public static void splitList(SNode head,SNode head1,SNode head2) {
SNode slowNode=head,fastNode=head;
if(head==null)
return;
//如果循环链表有奇数个节点，则fastNode.getNext()指向head
//如果循环链表有偶数个节点，则fastNode.getNext().getNext()指向head
while(fastNode.getNext()!=head&&fastNode.getNext().getNext()!=head) {
fastNode=fastNode.getNext().getNext();
slowNode=slowNode.getNext();
}
if(fastNode.getNext().getNext()==head) {
fastNode=fastNode.getNext();
}
//head1指向前半部分的head指针
head1=head;
//head2指向后半部分的指针
if(head.getNext()!=head)
head2=slowNode.getNext();
//把后半部分变成环
fastNode.setNext(slowNode.getNext());
//把前半部分变成环
slowNode.setNext(head);
}
4.有序链表中插入一个节点
/**
* 时间复杂度为O(n),空间复杂度为O(1)
* @param head
* @param newNode
* @return
*/
public static SNode insertSortedList(SNode head,SNode newNode) {
SNode current=head,temp=null;
if(head==null)
return newNode;
while(current!=null) {
temp=current;
current=current.getNext();
}
newNode.setNext(current);
temp.setNext(newNode);
return head;
}
5.1链表逆置
/**
* 时间复杂度为O(n),空间复杂度为O(1)
* @param head
* @return
*/
public static SNode reverseList(SNode head) {
SNode temp=null,nextNode=null;
while(head!=null) {
nextNode=head.getNext();
head.setNext(temp);
temp=head;
head=nextNode;
}
return temp;
}
5.2逐对逆置链表,假如初始链表为1 2 3 4 x,逐对逆置后为2 1 4 3 x
/**
* @param head
* @return
*/
public static SNode reversePairRecursive(SNode head) {
SNode temp;
if(head==null||head.getNext()==null)
return head;
else {
temp=head.getNext();
head.setNext(temp.getNext());
temp.setNext(head);
head=temp;
head.getNext().setNext(reversePairRecursive(head.getNext().getNext()));
return head;
}
}
6.判断两个链表是否相交成为一个单链表，若相交，得出两链表的相交节点
/**
* 思路：两链表相交之后的长度必然相等，先获得两链表的长度，让更长的链表先后移两链表长度差个单位，再一起向后遍历，直到出现两节点相等或到达表尾
* 时间复杂度为O(m,n),空间复杂度为O(1)
* @param list1
* @param list2
* @return
*/
public static SNode findIntersectingNode(SNode list1,SNode list2) {
int l1=0,l2=0,diff=0;
SNode head1=list1,head2=list2;
while(head1!=null) {
l1++;
head1=head1.getNext();
}
while(head2!=null) {
l2++;
head2=head2.getNext();
}
if(l1<l2) {
head1=list2;
head2=list1;
diff=l2-l1;
}else {
head1=list1;
head2=list2;
diff=l1-l2;
}
for(int i=0;i<diff;i++)
head1=head1.getNext();
while(head1!=null&&head2!=null) {
if(head1==head2)
return head1;
head1=head1.getNext();
head2=head2.getNext();
}
return null;
}
7.寻找链表的中间节点:设置两个指针，第一个指针的移动速度是第二个指针的两倍，当第一个指针到达表尾，第二个指针即指向中间节点
/**
* 时间复杂度为O(n),空间复杂度为O(1)
* @param head
* @return
*/
public static SNode findMiddle(SNode head) {
SNode point1=head,point2=head;
int i=0;
while(point1.getNext()!=null) {
if(i==0) {
point1=point1.getNext();
i=1;
}else if(i==1) {
point1=point1.getNext();
point2=point2.getNext();
i=0;
}
}
return point2;
}
8.检查链表长度是奇数还是偶数,每次后移两个元素,返回1表示奇数，返回0表示偶数
/**
* 时间复杂度为O(n/2)，空间复杂度为O(1)
* @param head
* @return
*/
public static int isLinkedListLengthEven(SNode head) {
while(head!=null&&head.getNext()!=null) {
head=head.getNext().getNext();
}
if(head==null)
return 0;
else
return 1;
}
9.合并两个有序链表
/**
* 时间复杂度为O(n)
* @param a
* @param b
* @return
*/
public static SNode mergeList(SNode a,SNode b) {
SNode result=null;
if(a==null)
return b;
if(b==null)
return a;
if(a.getData()<=b.getData()) {
result=a;
result.setNext(mergeList(a.getNext(), b));
}else {
result=b;
result.setNext(mergeList(a,b.getNext()));
}
return result;
}
10.从表尾开始输出链表
/**
* @param head
*/
public static void printListFromEnd(SNode head) {
if(head==null)
return;
printListFromEnd(head.getNext());
System.out.println(head.getData());
}
网友评论