（C语言）链表经典oj题（一）
- 题目1.链表的回文结构
- 题目2.相交链表
- 题目3.环形链表
- 题目4.环形链表II
- 题目5.复制带随机指针的链表
题目链接
思路：
1、先找到整段链表的中间结点，奇数个就是最中间的那个结点，偶数个的话就是中间两个的第二个。
2、然后从中间结点开始逆置结点，
3、最后同时从头结点head和中间结点rmid开始比对他们的值
由于中间结点之前的那个结点的next我们从始至终都没有改变 ， 所以说就能同时从头结点和中间结点开始比对。
什么时候停下来呢？这需要分情况处理
偶数个结点：若到rmid到NULL停止，head和rmid的值依然都相等，那么就是回文
奇数个结点：若head和rmid都到NULL停止，head和rmid的值依然都相等，那么就是回文
实现代码：
class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head) { //反转链表
struct ListNode* n1 = NULL;
struct ListNode* n2 = head;
struct ListNode* n3 = NULL;
while (n2) {
n3 = n2->next;
n2->next = n1;
n1 = n2;
n2 = n3;
}
return n1;
}
struct ListNode* middleNode(struct ListNode* head) { //找中间结点
//奇数个和偶数个
//快慢指针
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool chkPalindrome(ListNode* A) {
struct ListNode* head = A;
struct ListNode* mid = middleNode(A);
struct ListNode* rmid = reverseList(mid);
while (head && rmid) {
if (head->val != rmid->val) {
return false;
}
head = head->next;
rmid = rmid->next;
}
return true;
}
};
题目2.相交链表
题目链接
思路：
定义两个指针head1和head2分别记录headA和headB的值，先让他们分别走到链表的最后，并记录各自的长度，看是否有交点，没有交点直接返回NULL，
然后再定义两个指针longlist和shortlist再次分别记录headA和headB;通过计算A链表和B链表的差值的绝对值，让长的那个链表先走差值的绝对值步，最后两个链表再同时往前遍历，判断longlist和shortlist是否的地址相同，一旦相同就说明当前地址是两个单链表相交的起始节点，返回此时的地址即可。
实现代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode*Head1=headA;
struct ListNode*Head2=headB;//题目说 函数返回结果后，链表必须 保持其原始结构 。
if(headA==NULL||headB==NULL)
{
return NULL;
}
int length1=1;//两个链表同时往后走，都走到最后看是否“相交”，并且记录长度
while(Head1->next)
{
Head1=Head1->next;
length1++;
}
int length2=1;
while(Head2->next)
{
Head2=Head2->next;
length2++;
}
if(Head1!=Head2)//都走到最后不相交直接返回NULL
{
return NULL;
}
struct ListNode*longlist=headA;
struct ListNode*shortlist=headB;
if(length1
shortlist=headA;
longlist=headB;
}
int gap=abs(length2-length1);//求绝对值函数
//长的链表先走距离步
while(gap)
{
longlist=longlist->next;//长链表往后走距离的差之后
gap--;
}
while(longlist!=shortlist)//再同时往后走，找出并返回两个单链表相交的起始节点
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;
}
题目3.环形链表
题目链接
思路：定义一个快指针fast再定义一个慢指针slow，快指针一次走两步，慢指针一次走一步，如果有环的情况下，快指针一定会通过环的结构，与慢指针相遇。下面画了一幅动图供大家参考。
为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚
进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。
此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情
况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
如果没有环的情况下，那么就是前面链表经典oj题（一）里链表的中间结点问题了。
实现代码：
bool hasCycle(struct ListNode *head) {
struct ListNode *slow=head;
struct ListNode *fast=head;
while(fast&&fast->next)
//因为快指针一次走两步，如果当前链表没有环的时候，
//偶数个走到fast==NULL的时候停止，
//奇数个的话走到fast->next==NULL的时候停止
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)//在环中快指针一定有一个时刻能和慢指针重合
{
return true;
}
}
return false;
}
题目4.环形链表II
题目链接
思路：
解法一：普通解法，如果有环的情况下，定义一个快慢指针，从头开始往后先找在环中相遇的结点，然后将此处的结点的next置为NULL，相当于断开当前的环，那么就是前面的相交链表问题了。最后要注意恢复原来的链表。但是此方法工程量比较大。需要把前面的相交问题的代码加以完善才能解决此题。
解法二：公式推导解法，我们知道fast走的距离=2 * slow走的距离，假设进环前的长度是L，假设环的长度是C，假设入口点到相遇点距离是X。slow走的距离是L+X，fast走的距离是L+N * C+X，设slow进环前，fast在环里面转了N圈N>=1。
可得： 2(L+X)=L+X+N*C
（ L+X）=N * C
L=N * C - X
化简得：L=（N-1）*C+C-X
结论：一个指针A从头开始走，一个指针B从相遇点开始走他们会在入口点相遇。
实现代码：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
{
struct ListNode*meet=fast;
struct ListNode*myhead=head;
while(meet!=myhead)
{
myhead=myhead->next;
meet=meet->next;
}
return myhead;
}
}
return NULL;
}
题目5.复制带随机指针的链表
题目链接
思路：
1、拷贝原结点，并链接在原结点的后面。使原结点和拷贝结点建立一个链接关系，找到原结点，，就可以找到拷贝结点。
2、更新每个拷贝结点的random（关键步骤）
if(cur->random）
copy->random = cur->random->next；
3、将拷贝结点解下来，链接成新链表
struct Node* copyRandomList(struct Node* head) {
struct Node* cur=head;
struct Node* back=NULL;
struct Node* copy=NULL;
while(cur)//1.拷贝原结点，链接在原结点后面
{
copy=(struct Node*)malloc(sizeof(struct Node));
back=cur->next;
cur->next=copy;
copy->val=cur->val;
copy->next=back;
cur=back;
}//此时原链表的各个元素已经断开
cur=head;
while(cur)//2.更新每个拷贝结点的random
{
copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=cur->next->next;
}
cur=head;
struct Node* copyhead=NULL;
struct Node* copytail=NULL;
while(cur)//3.将拷贝结点解下来，链接成新链表
{
copy=cur->next;
back=cur->next->next;
cur->next=back;//
if(copyhead==NULL)
{
copyhead=copytail=copy;//头插，直接连上去不用更新结点
}
else
{
copytail->next=copy;
copytail=copytail->next;//尾插，需不需要更新尾结点，画图就可以知道//
}
// copytail=copytail->next;犯错之处
cur=back;
}
return copyhead;
}
总结：
1、链表题要多多画图，代码要跟着图走。
2、注意指针下一步要走向哪里？是不动？还是要跳到下一个结点上？每次循环过后要注意更新结点。
3、多做题，积累经验和方法，有些题目不是不会，只是从来都不知道有这样的方法。
