玩转链表，从这8道经典链表oj题开始

文章目录

1.移除链表元素

大体思路分析：用

cur

指针去遍历链表,用

prev

指针记录

cur

的前一个节点，如果

cur->val != val

，则

prev=cur，cur=cur->next

；如果

cur->val == val

，则用

next

指针记录

cur

指针的下一个节点，

free(cur),prev=next,cur=next,prev=cur;

继续如此循环。
但是如果第一个链表的数据就是

val

就又是一种情况。如果连续几个都是

val

又是什么情况呢？
下面我们画图来分析。

1. 常规情况：
2. 连续几个val： 我们发现常规情况也能处理连续几个val的情况。
3. 第一个就是val，意味着要改变头指针

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */struct ListNode*removeElements(struct ListNode* head,int val){struct ListNode* cur = head;struct ListNode* prev =NULL;while(cur){if(cur->val != val){
            prev = cur;
            cur = cur->next;}else{struct ListNode* next = cur->next;if(prev ==NULL){free(cur);
                head = next;
                cur = next;}else{free(cur);
                prev->next = next;
                cur = next;}}}return head;}

2. 反转链表

2.1 三指针翻转法

令指针

n1

等于

NULL

,

n2

等于

head

,

n3

记录

n2

的下一个，让

n1，n2

去倒指针的方向，

n3

记录下一个节点。

我们发现当

n2

指针等于

NULL

时，链表全部反转，所以

n2 == NULL

为结束条件。
特殊情况：

此时

n3

已经为

NULL

了，如果继续

n3=n3->next

，就出现了访问空指针的情况。所以这种情况也要判断一下。另外，如果头指针为

NULL

，直接

return NULL

；
代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */struct ListNode*reverseList(struct ListNode* head){if(head ==NULL)returnNULL;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;}

2.2 头插法

cur

取原链表节点，头插到

newHead

所在的链表，用

next

指针记录

cur

的下一个，同时更新

newHead

。

我们发现当

cur

走到

NULL

，遍历结束，链表完成反转。所以

cur==NULL

为循环结束条件。
代码实现：

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

3. 链表的中间节点

1. 奇数个数据：
2. 偶数个数据 我们发现结束条件为fast为空或fast->next为空。

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

4. 链表的倒数第k个节点

fast

先走

k

步，然后

fast

和

slow

同时走，当

fast

走到空，

slow

就是倒数第k个节点。

代码：

struct ListNode*FindKthToTail(struct ListNode* pListHead,int k ){struct ListNode* slow,*fast;
    slow = fast = pListHead;while(k--){if(fast ==NULL)returnNULL;
        fast = fast->next;}while(fast){
        slow = slow->next;
        fast = fast->next;}return slow;}

5.合并两个有序链表

每次取小的节点尾插到新链表。如果

list1

先走完，把剩下的

list2

直接尾插给

tail

，反之，剩下的

list1

尾插给

tail

；

特殊情况处理：当

list1

为空，返回

list2

，当

list2

为空，返回

list1

。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */struct ListNode*mergeTwoLists(struct ListNode* list1,struct ListNode* list2){if(list1 ==NULL){return list2;}if(list2 ==NULL){return list1;}struct ListNode* head=NULL,*tail=NULL;while(list1 && list2){if(list1->val < list2->val){if(tail ==NULL){
                head = tail = list1;}else{
                tail->next = list1;
                tail = list1;}
            list1 = list1->next;}else{if(tail ==NULL){
                head = tail = list2;}else{
                tail->next = list2;
                tail = list2;}
            list2 = list2->next;}}if(list1){
        tail->next = list1;}if(list2){
        tail->next = list2;}return head;}

6. 链表分割

遍历原链表，把小于x的插入到一个链表1，把大于等于x的插入到一个链表2，链表1和链表2连接起来。

我们再考虑一下其他情况：


这种情况链表就成环了，此时程序死循环。只要把greattail->next== NULL就行了；
代码：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode*partition(ListNode* pHead,int x){// write code herestruct ListNode*head1,*head2,*tail1,*tail2;
         head1=tail1=(struct ListNode*)malloc(sizeof(struct ListNode));
         head2=tail2=(struct ListNode*)malloc(sizeof(struct ListNode));
        tail1->next=NULL;
        tail2->next=NULL;struct ListNode* cur=pHead;while(cur){if(cur->val<x){
                tail1->next=cur;
                tail1=tail1->next;}else{
                tail2->next=cur;
                tail2=tail2->next;}
            cur=cur->next;}
    tail1->next=head2->next;
        tail2->next=NULL;//**必须要有，不然会在某些极端测试用例下会形成一个环，//那便 是死循环了，栈溢出。**
        pHead=head1->next;free(head1);free(head2);return pHead;}};

7.链表的回文结构

思路：先找到链表的中间节点，然后从中间节点开始把链表逆置，rHead，A同时走并比较。如果有不相等的，就说明不是回文，return false；如果有一个走完，return ture；

我们发现，偶数和奇数，这种方法都适用，因为即使把链表后半段逆置了，2也是指向3的。
代码：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

class PalindromeList {
public:struct ListNode*middleNode(struct ListNode* head){struct ListNode* slow,*fast;
    slow = fast = head;while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;}return slow;}struct ListNode*reverseList(struct ListNode* head){struct ListNode* newHead =NULL;struct ListNode* cur = head;while(cur){struct ListNode* next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = next;}return newHead;}
    bool chkPalindrome(ListNode* A){struct ListNode *mid=middleNode(A);struct ListNode *rHead=reverseList(mid);while(A&&rHead){if(A->val!=rHead->val){return false;}else{ 
                A=A->next; 
                rHead=rHead->next;}}return true;}};

8.相交链表

思路：

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */struct ListNode *getIntersectionNode(struct ListNode *headA,struct ListNode *headB){struct ListNode* tailA = headA,*tailB = headB;int lenA =1, lenB =1;while(tailA->next){
        tailA = tailA->next;++lenA;}while(tailB->next){
        tailB = tailB->next;++lenB;}if(tailA!=tailB){returnNULL;}struct ListNode* shortList = headA,*longList = headB;if(lenA > lenB){
        longList = headA;
        shortList = headB;}int gap =abs(lenA-lenB);while(gap--){
        longList = longList->next;}while(shortList && longList){if(shortList == longList){return shortList;}
        shortList = shortList->next;
        longList = longList->next;}returnNULL;}