【题目集2】链表经典题目

移除链表元素

思路：先要判断这个链表是不是空链表，如果是空链表就直接返回NULL，就可以

代码：

struct ListNode* removeElements(struct ListNode* head, int val){
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode* cur = head;
    struct ListNode* newnode, *tail;
    newnode = tail = NULL;
    while(cur != NULL)
    {
        if(cur->val != val)
        {
            if(tail == NULL)
            {
                newnode = tail = cur;
            }
            else 
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    if(tail)
    {
        tail->next = NULL;
    }
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

注意：这个题最后需要注意的是tail的下一个应该也是NULL，否则就有可能将最后一个链表连接。

合并两个有序链表

思路：重新用一个新的链表头来表示节点，如果小于的数就加入到链表当中。

代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1 == NULL) {
        return list2;
    }
    if(list2 == NULL) {
        return list1;
    }
    struct ListNode* head, *tail;
    head = tail = NULL;
    while(list1 && list2) {
        if(list1->val < list2->val) {
            if(tail == NULL) {
                head = tail = list1;
            }else {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }else {
            if(tail == NULL) {
                head = tail = list2;
            }else {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if(list1) {
        tail->next = list1;
    }
    if(list2) {
        tail->next = list2;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

链表的中间节点

思路：这个题目只需要根据速度差，一个指针的速度是另一个指针速度的二倍，当快的指针到达终点的时候，慢指针刚好到达中间节点。

代码：

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *fast, *slow;
    fast = slow = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9

链表中的倒数第k个结点

思路：先让快的链表走k步，然后两个指针一起往后移动，如果快的指针到达最后，慢的指针就是最后的结果。

代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
   // write code here
   struct ListNode *fast, *slow;
   fast = slow = pListHead;
   while(k) {
       if(fast == NULL) {
           return NULL;
       }
       fast = fast->next;
       k --;
   }
   while(fast) {
       fast = fast->next;
       slow = slow->next;
   }
   return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

反转链表

代码：

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL) {
        return NULL;
    }
    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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

链表分割

对于最后一个数字，还有不同的情况考虑：

代码：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lessTail->next = greaterTail->next = NULL;
        struct ListNode* cur = pHead;
        while(cur) {
            if(cur->val < x) {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }else {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        pHead = lessHead->next;
        free(lessHead);
        free(greaterHead);
        return pHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

链表的回文结构

思路：直接找到中间节点，然后反转中间节点到最后的链表就可以。

代码：

struct ListNode* findMid(struct ListNode* A) {
    struct ListNode* slow = A, *fast = A;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

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

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid = findMid(A);
        struct ListNode* rhead = reverse(mid);
        while(A && rhead) {
            if(A->val != rhead->val) {
                return false;
            }
            A = A->next;
            rhead = rhead->next;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

相交链表

思路：找到两个其中长的一个链表，然后走差值步，一起走看是否有相等的地址。

代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
        struct ListNode* curA = headA, *curB = headB;
        int lenA = 0, lenB = 0;
    	//分别找到链表A和链表B的长度
        while(curA) {
            lenA ++;
            curA = curA->next;
        }
        while(curB) {
            lenB ++;
            curB = curB->next;
        }
    	//如果最后不相等，则绝对不存在公共节点
    	//如果相等，则一定存在公共节点
        if(curA != curB) {
            return NULL;
        }
        int gap = abs(lenA - lenB);
    	//假设A>B
        struct ListNode* LongList = headA, *ShortList = headB;
        if(lenB > lenA) {
            LongList = headB;
            ShortList = headA;
        }
        while(gap --) {
            LongList = LongList->next;
        }
        while(LongList != ShortList) {
            LongList = LongList->next;
            ShortList = ShortList->next;
        }
        return LongList;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

环形链表

思路：两个指针，一个指针每次跑一步，另一个指针每次跑两步，如果有环两个指针肯定能够相遇。

代码：

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow = head, *fast = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11

环形链表II(找到如环的节点)

结论：让一个指针从链表的起始位置开始遍历链表，同时让一个指针从判环相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

代码：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head, *fast = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) {
            struct ListNode* meet = slow;
            while(head != meet) {
                head = head->next;
                meet = meet->next;
            }
            return head;
        }
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复制带随机指针的链表

思路：

1. 拷贝节点在源节点的后面

代码实现：

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
    while(cur) {
        struct Node* next = cur->next;
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        cur->next = copy;
        copy->next = next;
        cur = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2. 设置拷贝节点的random

代码实现：

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
    while(cur) {
        struct Node* next = cur->next;
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        cur->next = copy;
        copy->next = next;
        cur = next;
    }
    //设置拷贝节点的random
    cur = head;
    while(cur) {
        struct Node* copy = cur->next;
        if(cur->next == NULL) {
            copy->random = NULL;
        }else {
            copy->random = cur->random->next;
        }
        cur = cur->next->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3. 拷贝节点解下来，连接组成拷贝链表

代码实现：

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
    while(cur) {
        struct Node* next = cur->next;
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        cur->next = copy;
        copy->next = next;
        cur = next;
    }
    cur = head;
    while(cur) {
        struct Node* 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, *copyTail = NULL;
    while(cur) {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        cur->next = next;
        if(copyTail == NULL) {
            copyHead = copyTail = copy;
        }else {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
        cur = next;
    }
    return copyHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36