例题
单链表翻转 LeetCode 206
这个问题可以使用递归和非递归两种方法解决。
递归算法实现:
ListNode* reverseList(ListNode* head)
{
if(NULL == head || NULL == head->next)
return head;
ListNode * p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
非递归算法实现:
ListNode* reverseList(ListNode* head) {
ListNode *curr = head;
if (curr == NULL) {
return NULL;
}
ListNode *prev = NULL, *temp = NULL;
while (curr != NULL) {
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
return prev;
}
单链表判断是否有环 LeetCode 141
最容易想到的思路是存一个所有 Node 地址的 Hash 表,从头开始遍历,将 Node 存到 Hash 表中,如果出现了重复,则说明链表有环。
一个经典的方法是双指针(也叫快慢指针),使用两个指针遍历链表,一个指针一次走一步,另一个一次走两步,如果链表有环,两个指针必然相遇。
双指针算法实现:
bool hasCycle(ListNode *head) {
if (head == nullptr) {
return false;
}
ListNode *fast,*slow;
slow = head;
fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
单链表找环入口 LeetCode 141
作为上一题的扩展,为了找到环所在的位置,在快慢指针相遇的时候,此时慢指针没有遍历完链表,再设置一个指针从链表头部开始遍历,这两个指针相遇的点,就是链表环的入口。
算法实现:
ListNode *detectCycle(ListNode *head) {
if (head == nullptr) {
return nullptr;
}
ListNode *fast,*slow;
slow = head;
fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode *slow2 = head;
while (slow2 != slow) {
slow = slow->next;
slow2 = slow2->next;
}
return slow2;
}
}
return nullptr;
}
单链表找交点 LeetCode 160
和找环的方法类似,同样可以使用 Hash 表存储所有节点,发现重复的节点即交点。
一个容易想到的方法是,先得到两个链表的长度,然后得到长度的差值 distance,两个指针分别从两个链表头部遍历,其中较长链表指针先走 distance 步,然后同时向后走,当两个指针相遇的时候,即链表的交点:
int getListLength(ListNode *head) {
if (head == nullptr) {
return 0;
}
int length = 0;
ListNode *p = head;
while (p!=nullptr) {
p = p->next;
length ++;
}
return length;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lengthA = getListLength(headA);
int lengthB = getListLength(headB);
if (lengthA > lengthB) {
std::swap(headA, headB);
};
int distance = abs(lengthB - lengthA);
ListNode *p1 = headA;
ListNode *p2 = headB;
while(distance--) {
p2 = p2->next;
}
while (p1 != nullptr && p2 != nullptr) {
if (p1 == p2)
return p1;
p1 = p1->next;
p2 = p2->next;
}
return NULL;
}
另一个较快的方法时,两个指针 pa,pb 分别从 headA,headB开始遍历,当 pa 遍历到尾部的时候,指向 headB,当 pb 遍历到尾部的时候,转向 headA。当两个指针再次相遇的时候,如果两个链表有交点,则指向交点,如果没有则指向 NULL:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pa = headA;
ListNode *pb = headB;
while (pa != pb) {
pa = pa != nullptr ? pa->next : headB;
pb = pb != nullptr ? pb->next : headA;
}
return pa;
}
单链表找中间节点 LeetCode 876
用快慢指针法,当快指针走到链表结尾时,慢指针刚好走到链表的中间:
ListNode* middleNode(ListNode* head) {
ListNode *slow = head;
ListNode *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
单链表合并 LeetCode 21
两个链表本身都是排序过的,把两个链表从头节点开始,逐个节点开始进行比较,最后剩下的节点接到尾部:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if (l1 == nullptr) {
return l2;
}
if (l2 == nullptr) {
return l1;
}
ListNode dummy(-1);
ListNode *p = &dummy;
for (; l1 && l2; p = p->next) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
}
p->next = l1 != nullptr ? l1 : l2;
return dummy.next;
}