【数据结构】经典链表题目详解集合（反转链表、相交链表、链表的中间节点、回文链表）

一、反转链表

1、程序详解

题目：给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 ：（将链表逆置）

1. 方法一：创建新链表。 遍历原链表，并将节点依次头插到新链表中。
2. 方法二：创建三个指针 。 通过指针的不断移动，依次完成反转
   创建三个结构体指针：n1、n2、n3
   令 n1指向空，n2指向头节点，n3指向头结点的下一个节点
   
   分为两个步骤：
   1、n2->next=n1, 令n2指向n1
   2、n1、n2、n3不断向后移动
   

2、代码

struct ListNode* reverseList(struct ListNode* head){if(head==NULL)return head;struct ListNode* n1, *n2, *n3;n1=NULL, n2=head, n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;
}

二、相交链表

1、程序详解

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

注：根据一个节点只能有一个next，相交链表一定是Y型的。

当然也有两种方法：（一定要用地址来判断）

• 方法一：暴力求解，双层循环。
  A链表中的节点依次与B链表中的所有节点相比较，此时,时间复杂度为O(N^2)
• 方法二：双指针
  1、找出A链表与B链表长度，相减得差值k
  2、让长链表的指针先走k步
  3、A与B的指针同时走，并相比较
  

2、代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode * curA = headA, *curB = headB;int len1 = 1, len2=1;  //用len1，len2来记录两链表的长度，但在循环里面少记录一个，故初始化为1while(curA->next){curA = curA->next;len1++;}while(curB->next){curB = curB->next;len2++;}//若尾节点不相等，则两链表一定不相交if(curA != curB){return NULL;}//相交//找出长链表和短链表struct ListNode * longList = headA, *shortList = headB;int gre = abs(len1-len2);if(len1<len2){longList = headB;shortList = headA;}//找出长短链表后，让长链表先走差步while(gre--){longList = longList->next;}//两链表同时走while(longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
}

三、链表的中间节点

1、程序详解

题目：给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

• 方法：快慢指针
  若使快指针的速度始终是慢指针的二倍，那么当快指针走到链表结尾，慢指针刚好走到链表的中间。
  

2、代码

struct ListNode* middleNode(struct ListNode* head) {//快慢指针,快指针走两步，慢指针走一步struct ListNode* fast = head, *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

四、回文链表

1、程序详解

题目：给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表。如果是，返回 true ；否则，返回 false 。

• 方法：
  1、找到中间节点
  2、将中间节点之后的节点进行反转
  3、将中间节点之前的与反转后的节点 的val值进行比较

故回文链表综合了 反转链表与链表的中间节点，了解了这两个题目方法后，我们只需写进行比较的代码。

2、代码

//找中间节点
struct ListNode *fac1(struct ListNode * head)
{struct ListNode * fast=head, *slow=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}
//反转
struct ListNode *fac2(struct ListNode * head)
{struct ListNode * n1, *n2, *n3;n1=NULL, n2=head, n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;
}
bool isPalindrome(struct ListNode* head) {struct ListNode * mid = fac1(head);struct ListNode * rmid = fac2(mid);//进行比较while(rmid && head){if(rmid->val != head->val)return false;rmid=rmid->next;head=head->next;}return true;
}