一、反轉鏈表

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;
}