LeetCode刷题——单链表（详细图解）

题目目录

1.反转链表

方法一：暴力改链表方向

思路就是直接把箭头全改为反向
要注意的是要三个结构体指针n1(要改的前一个), n2(要改的), n3(要改的后面一个)，依次向后遍历就能完成。
代码如下 ：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */structListNode*reverseList(structListNode* head){if(head ==NULL){returnNULL;}structListNode* n1 =NULL;structListNode* n2 = head;structListNode* n3 = head->next;while(n3 !=NULL){
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        n3 = n3->next;}
    n2->next = n1;return n2;}

方法二：迭代法

用尾插的方法迭代：
创建一个新的尾（NULL），原链表从左向右依次插入新链表就能完成反转，如图：
开始

过程

结束

要注意的是newHead的位置要改变到新链表头部，以返回新链表。

代码如下 ：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */structListNode*reverseList(structListNode* head){if(head ==NULL|| head->next ==NULL){return head;}structListNode* newHead =NULL;structListNode* cur = head;structListNode* next = cur->next;while(cur){structListNode* next = cur->next;
         cur->next = newHead;
         newHead = cur;
         cur = next;}return newHead;}

2.链表的中间结点

方法一：暴力解法

遍历链表计算总共数目，结果 /2 就为中间值，再遍历到这个位置
代码如下 ：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */structListNode*middleNode(structListNode* head){int count =0;structListNode* cur = head;while(cur){
        count++;
        cur = cur->next;}
    count = count/2;structListNode* curr = head;while(count--){
         curr = curr->next;}return curr;}

方法二：快慢指针

这里的快慢不是指速度，而是指针移动的距离大小。
我们可以用两个指针
fast：一次移动2位
slow：一次移动1位
当fast移动完slow就会移动到中间。
如图：
开始

结束

代码如下 ：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */structListNode*middleNode(structListNode* head){structListNode* slow = head;structListNode* fast = head;while(fast && fast->next)//顺序不能变{
        slow = slow->next;
        fast = fast->next->next;}return slow;}

这里要注意while的判断部分顺序不能变，不然会对空指针引用（偶数的情况下）

3.链表中倒数第k个节点

这道题其实就是上面一道题的进阶也是用快慢指针的方法。k为快指针比慢指针多走的位数。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */structListNode*getKthFromEnd(structListNode* head,int k){structListNode* slow = head;structListNode* fast = head;while(k--){if(fast ==NULL){returnNULL;}
        fast = fast->next;}while(fast !=NULL){
        slow = slow->next;
        fast = fast->next;}return slow;}

4.回文链表

我们可以发现这道题是前几个题的总和。
1️⃣先用快慢指针找到位置
2️⃣在旋转后边的
3️⃣最后进行比较

1️⃣图：

2️⃣图：

如果是奇数个：

最后两个同时遍历比较就好了
代码如下 ：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

bool isPalindrome(structListNode* head){structListNode* fast = head;structListNode* slow = head;while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;}//旋转后半部分//尾插structListNode* newnode =NULL;while(slow){structListNode* tmp = slow;
        slow = slow->next;
        tmp->next = newnode;
        newnode = tmp;}//比较//奇数个中间的前一个的next没变structListNode* hcur = head,*ncur = newnode;while(hcur && ncur){if(hcur->val != ncur->val){return false;}else{
        hcur = hcur->next;
        ncur = ncur->next;}}return true;}

5.合并两个有序链表

先设置个新的头部取两个链表的最小值放进去，然后依次比较两条链表的较小值尾插到新链表。
如图：
开始

过程


结束

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){if(list1 ==NULL){return list2;}if(list2 ==NULL){return list1;}structListNode* head =NULL,*tail =NULL;//先取最小的当头节点if(list1->val < list2->val){
        head = tail = list1;
        list1 = list1->next;}else{
       head = tail = list2;
       list2 = list2->next;}//尾插while(list1 && list2){if(list1->val < list2->val){
            tail->next = list1;
            list1 = list1->next;}else{
            tail->next = list2;
            list2 = list2->next;}
        tail = tail->next;}if(list1 ==NULL){
        tail->next = list2;}else{
        tail->next = list1;}return head;}

6.分割链表

要我们分割链表，我们可以把小于x的节点放到 smallnode 链表里，把大于等于x的节点放到 largenode 链表里再把两个链表相连返回即可。
如图：
开始

过程


结束

连接

代码如下 ：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */structListNode*partition(structListNode* head,int x){if(head ==NULL){return head;}structListNode* largenode =(structListNode*)malloc(sizeof(structListNode));
    largenode->next =NULL;structListNode* smallnode =(structListNode*)malloc(sizeof(structListNode));
    smallnode->next =NULL;structListNode* ltail = largenode,*stail = smallnode;while(head){if(head->val < x){
            stail->next = head;
            stail = stail->next;}else{
            ltail->next = head;
            ltail = ltail->next;}
        head = head->next;}
    stail->next = largenode->next;
    ltail->next =NULL;structListNode* phead = smallnode->next;free(smallnode);free(largenode);return phead;}

7.相交链表

首先说方法，把两个链表都遍历一遍算出长度，顺便把最后一个元素比较，如果不同，则不相交，因为只要有交点，后边的元素必全部重合。长度的差值就为长链表先走的位数，可以参考前面的快慢指针的方法，此时两个链表同时往后才有可能找到交点。
用题中所给的例子：

代码如下 ：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){if(headA ==NULL|| headB ==NULL){returnNULL;}structListNode* curA = headA,*curB = headB;int lenA =0, lenB =0;while(curA->next){
        curA = curA->next;
        lenA++;}while(curB->next){
        curB = curB->next;
        lenB++;}if(curB != curA){returnNULL;}structListNode* longlist = headA,*shortlist = headB;if(lenA < lenB){
        longlist = headB;
        shortlist = headA;}//长的先走gap步//abs是绝对值的意思int gap =abs(lenA-lenB);while(gap--){
        longlist = longlist->next;}while(longlist != shortlist){
        longlist = longlist->next;
        shortlist = shortlist->next;}return longlist;}