链表
链表是一种非顺序的数据结构,在面试当中经常被问到,本篇将会讨论几个常见的关于链表的算法题。
首先定义链表的节点和算法当中需要用到的工具函数。
java版本
//节点
public class Node {
public int value;
public Node next;
public Node(int value){
this.value = value;
}
}
//将节点往后移动step步
public static Node move(Node root, int step){
if(root == null || step<0){
return root;
}
Node cur = root;
for(int i=0;i<step;i++){
cur = cur.next;
if(cur == null){
break;
}
}
return cur;
}
//获取链表的长度
public static int nodeLength(Node root){
int length = 0;
Node cur = root;
while(cur != null){
cur = cur.next;
length ++;
}
return length;
}
c++版本
//节点
class Node{
public :
int value;
Node* next;
Node(int value){
this->value = value;
this->next = NULL;
}
};
//将节点往后移动position步
Node* move(Node *node,int step){
if(node == NULL || step < 0){
return NULL;
}
Node* cur = node;
for(int i=0;i<step;i++){
cur = cur->next;
if(cur == NULL){
break;
}
}
return cur;
}
//获取链表的长度
int nodeLength(Node *node){
int length = 0;
Node* cur = node;
while(cur != NULL){
cur = cur->next;
length ++ ;
}
return length;
}
1.链表反转
题目:
给定一个单向链表的头结点对像,请写出一个函数,反转该链表并输出反转后链表的头结点。
分析:
其实这一题的思路挺简单的,对于每个节点只需要把它的next指向它的前一个节点就可以了。但是需要考虑这样几个问题
- 空链表或者只有一个节点的链表;
- 当一个节点指向它前一个节点的时候,链表断裂了;
首先我们看第一个问题,如果是空链表或者只有一个节点,其实就不用反转,直接返回就可以了;
再来看第二个问题,从下面的图中可以看出节点7指向了它的前一个节点,此时链表断裂,因此我们必须要事先保存节点9。所以对于链表的每个节点,都必须要知道其前一个节点和后一个节点。特殊情况,对于头节点,其前一个节点是null,尾节点,后一个节点是null。
代码:
java版本
public static Node reverse(Node root){
if(root == null || root.next == null){
return root;
}
Node pre = null;//当前节点的前一个节点
Node current = root;//当前节点
Node next = current.next;//当前节点的后一个节点
while(next != null){
current.next = pre;
pre = current;
current = next;
next = current.next;
}
current.next = pre;
return current;
}
c++版本
Node* reverse(Node* root){
if(root == NULL || root->next == NULL){
return root;
}
Node* pre = NULL;//当前节点的前一个节点
Node* current = root;//当前节点
Node* next = current->next;//当前节点的后一个节点
while(next != NULL){
current->next = pre;
pre = current;
current = next;
next = current->next;
}
current->next = pre;
return current;
}
2.链表中间节点
题目:
- 2.1 给定一个单向链表,求链表的中间节点,若节点总数为奇数,则返回中间节点,若为偶数,则返回中间两个节点中的任意一个。(可否一次遍历解决问题)
- 2.2 接上题,用类似的方法可否判断一个单向链表中是否含有环,同样要求在一次遍历中完成。
####分析2.1:
看到这个题目,第一反应就是先得到链表的长度,知道了链表的长度就能够知道中间节点的位置。不过这样子需要遍历两次,不符合题目的要求。
换一种思路,可以把链表想象成跑道,每个人跑步的速度不一样,如果A的速度是B的两倍,那么当A跑到终点的时候,B恰好处在跑道中间的位置。因此遍历链表的时候,也可以使用这种方法。
如下图所示,遍历的时候使用快慢两个指针,每次慢指针走一步,快指针走两步,这样当快指针到达终点的时候,慢指针正好在中间。
代码2.1:
java版本
public static Node midNode(Node root){
if(root == null || root.next == null){
return root;
}
Node cur1 = root;
Node cur2 = root;
while(true){
cur2 = Util.move(cur2,2);//每次移动两步
if(cur2 == null){
break;
}else{
cur1 = Util.move(cur1,1);//每次移动一步
}
}
return cur1;
}
c++版本
Node* midNode(Node* root){
if(root == NULL || root->next == NULL){
return root;
}
Node* cur1 = root;
Node* cur2 = root;
while(true){
cur2 = move(cur2,2);//每次移动两步
if(cur2 == NULL){
break;
}else{
cur1 = move(cur1,1);//每次移动一步
}
}
return cur1;
}
分析2.2
如果一个链表没有环,则一定会有一个尾节点,next指向null;
如果链表里面有环,同样的采用上面的思想,使用一快一慢两个指针遍历链表,最终这两个指针都会进入到环当中,快指针会追上慢指针,并在某个节点相遇。
代码2.2
Java版本
//判断链表是否有环,true有环,false无环
public static Boolean isCircle(Node root){
if(root == null || root.next == null){
return false;
}
Node fast = root;
Node slow = root;
while(true){
fast = move(fast,2);
slow = move(slow,1);
if(fast == null || slow == null){//无环
return false;
}else if(fast == slow){//有环
return true;
}
}
}
c++版本
bool isCircle(Node* root){
if(root == NULL || root->next == NULL){
return false;
}
Node* fast = root;
Node* slow = root;
while(true){
fast = move(fast,2);
slow = move(slow,1);
if(fast == NULL || slow == NULL){//无环
return false;
}else if(fast == slow){//有环
return true;
}
}
}
3.找公共节点
题目:
给定两个单向链表,请找出它们的第一个公共节点
###分析:
两个单向链表,如果它们有公共节点,那么它们一定是Y形状。
先考虑如果两个链表的长度相等,那么很容易想到,直接对两个链表遍历,并比较当前节点,一旦发现节点相同,则这个节点就是第一个公共节点。
如果链表的长度不相等呢?如下图不等长链表所示,第一个链表长度为6,第二个链表长度为7。我们可以先将第二条链表往后移动1步,这样剩下的链表长度就和第一条链表长度相等,这样就可以转化成为第一种情况了。
代码:
java版本
public static Node commonNode(Node root1,Node root2){
if(root1 == null || root2 == null){
return null;
}
Node cur1 = root1;
Node cur2 = root2;
int length1 = nodeLength(cur1);//链表1的长度
int length2 = nodeLength(cur2);//链表2的长度
cur1 = root1;
cur2 = root2;
if(length1 > length2){
cur1 = move(cur1,length1-length2);//链表1往后移动length1-length2步
}else if(length2 > length1){
cur2 = move(cur2,length2-length1);//链表2往后移动length2-length1步
}
return getCommonNode(cur1,cur2);
}
//相同长度链表获取公共节点
private static Node getCommonNode(Node cur1,Node cur2){
if(cur1 == null || cur2 == null){
return null;
}
while(cur1 != cur2 && cur1!=null && cur2 !=null){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
c++版本
Node* commonNode(Node* root1,Node* root2){
if(root1 == NULL || root2 == NULL){
return NULL;
}
Node* cur1 = root1;
Node* cur2 = root2;
int length1 = nodeLength(cur1);//链表1的长度
int length2 = nodeLength(cur2);//链表2的长度
if(length1 > length2){
cur1 = move(cur1,length1-length2);//链表1往后移动length1-length2步
}else if(length2>length1){
cur2 = move(cur2,length2-length1);//链表2往后移动length2-length1步
}
return getCommonNode(cur1,cur2);
}
//相同长度链表获取公共节点
Node* getCommonNode(Node* cur1,Node* cur2){
if(cur1 == NULL || cur2 == NULL){
return NULL;
}
while(cur1!=cur2 && cur1!=NULL && cur2!=NULL){
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
4.链表排序
题目:
- 4.1 给定一个单向链表,其节点的value为整数,请根据value的大小对链表进行升幂排序,并给出实现的时间和空间复杂度。
- 4.2 能否在时间复杂度O(nlogn)的情况下完成排序?
分析4.1:
其实无论对于数组或者链表,排序的思想都是一样的。
这里采用选择排序,排序过程如下图所示,第一趟选出链表当中最小的节点,并与头节点交换值,第二趟选择链表当中次小的节点…,直到所有的链表按照升幂排列好。其时间复杂度是O(n2),空间复杂度是O(1)。
代码4.1:
java版本
//选择排序
public static Node selectSort(Node root){
if(root == null || root.next == null){
return root;
}
Node cur = root;
while(cur != null){
Node minNode = findMin(cur);
//将最小节点的值与当前节点的值交换
int tmp = cur.value;
cur.value = minNode.value;
minNode.value = tmp;
cur = cur.next;
}
return root;
}
//找到最小节点
private static Node findMin(Node start){
if(start == null){
return null;
}
Node dst = start;
int minvalue = start.value;
Node cur = start.next;
while(cur != null){
if(cur.value < minvalue){
minvalue = cur.value;
dst = cur;
}
cur = cur.next;
}
return dst;
}
c++版本
Node* selectSort(Node* root){
if(root == NULL || root->next == NULL){
return root;
}
Node* cur = root;
while(cur != NULL){
Node* minNode = findMin(cur);
//将最小节点的值与当前节点的值交换
int tmp = cur->value;
cur->value = minNode->value;
minNode->value = tmp;
cur = cur->next;
}
return root;
}
//找到最小节点
Node* findMin(Node* start){
if(start == NULL){
return NULL;
}
Node* dst = start;
int minvalue = start->value;
Node* cur = start->next;
while(cur != NULL){
if(cur->value < minvalue){
minvalue = cur->value;
dst = cur;
}
cur = cur->next;
}
return dst;
}
分析4.2:
时间复杂度为O(nlogn)的排序算法,很容易让人想到快速排序和归并排序,这里使用归并排序的方法。
归并排序的思想是将一个比较复杂的问题,拆分成多个简单的问题,解决完简单问题之后,再将其结果合并。
如下图所示,先将链表通过中间节点递归拆分成多个子链表,然后将子链表排序合并,最后得到一个排好序的链表。
代码4.2:
java版本
//归并排序
public static Node mergeSort(Node root){
if(root == null || root.next == null){
return root;
}
//找到链表的中间节点
Node mid = midNode(root);
//将链表拆成root和root2两个子链表
Node root2 = mid.next;
mid.next = null;
//递归
Node first = mergeSort(root);
Node second = mergeSort(root2);
//合并
return merge(first,second);
}
//合并两个已经排序的链表
private static Node merge(Node root1,Node root2){
if(root1 == null || root2 == null){
return null;
}
Node head;
Node head1 = root1;
Node head2 = root2;
Node cur;
if(head1.value < head2.value){
head = head1;
head1 = head1.next;
}else{
head = head2;
head2 = head2.next;
}
cur = head;
while(head1!=null && head2!=null){
if(head1.value < head2.value){
cur.next = head1;
head1 = head1.next;
}else{
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
if(head1 != null){
cur.next = head1;
}else if(head2 != null){
cur.next = head2;
}
return head;
}
c++版本
//归并排序
Node* mergeSort(Node* root){
if(root == NULL || root->next == NULL){
return root;
}
//找到链表的中间节点
Node* mid = midNode(root);
//将链表拆成root和root2两个子链表
Node* root2 = mid->next;
mid->next = NULL;
//递归
Node* first = mergeSort(root);
Node* second = mergeSort(root2);
//合并
return merge(first,second);
}
//合并两个已经排序的链表
Node* merge(Node* root1,Node* root2){
if(root1 == NULL || root2 == NULL){
return NULL;
}
Node* head;
Node* head1 = root1;
Node* head2 = root2;
Node* cur;
if(head1->value < head2->value){
head = head1;
head1 = head1->next;
}else{
head = head2;
head2 = head2->next;
}
cur = head;
while(head1!=NULL && head2!=NULL){
if(head1->value < head2->value){
cur->next = head1;
head1 = head1->next;
}else{
cur->next = head2;
head2 = head2->next;
}
cur = cur->next;
}
if(head1 != NULL){
cur->next = head1;
}else if(head2 != NULL){
cur->next = head2;
}
return head;
}
总结
使用链表需要注意一些边界条件,比如空链表或者只有一个节点的链表,这种情况都要做特殊处理。
另外也要特别小心链表断裂的情况,比如第一题链表反转以及第四题归并排序当中都将链表打断了,我们需要考虑清楚这其中的逻辑,不然最后就无法得到我们想要的结果。