链表 leetcode题目总结 c++

作者: 什锦甜 | 来源:发表于2018-05-30 16:30 被阅读71次

链表

链表和数组最大的区别在于，链表不支持随机访问，不像数组可以对任意一位的数据进行访问，链表只能从头一个一个往下访问，寻找下一个元素，像穿针引线似的。也正因为链表的这种特点，增大了链表题目的难度。

本文主要讨论的是单链表，单链表中的链表结点结构体定义如下

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

由上面的代码可以看出，每个结点包含两个域，一个是val表示结点的值，一个是next指针，指向下一个结点。

1）做链表类题目的关键是画图，将链表指针指向的内存的变化用图表示出来。
2）链表类题目还有一个重要的技巧是设置虚拟头结点。在做题的时候，头结点(head)常常要特殊处理，因为head结点没有前一个结点，这就决定了头节点和后续节点的处理方法不同。但是如果在头结点前加了一个虚拟头节点，那它就可以用正常的方法来处理了。

虚拟头节点定义如下：

ListNode* dummyHead = new ListNode(0); //新建一个结点，value为0
dummyHead->next = head; //让它next指针指向头结点

虚拟头结点

相关题目

leetcode #21. Merge Two Sorted Lists 合并两个链表
leetcode #206. Reverse Linked List 翻转链表
leetcode #92. Reverse Linked List II 翻转链表中指定区间的结点
leetcode #83. Remove Duplicates from Sorted List 删除链表中重复元素
leetcode #2. Add Two Numbers 将两个链表转化成整数并相加，再存入链表中
leetcode #445. Add Two Numbers II** 和上题类似，但更难一些
leetcode #237. Delete Node in a Linked ListDelete Node in a Linked List 删除指定结点
leetcode #328. Odd Even Linked List 奇偶链表
leetcode #19. Remove Nth Node From End of List 删除倒数第n个结点

leetcode #21. Merge Two Sorted Lists 合并两个链表
题目：Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        if(l1->val > l2->val){
            ListNode *tmp = l2;
            tmp->next = mergeTwoLists(l1, l2->next);
            return tmp;
        }
        else{
            ListNode *tmp = l1;
            tmp->next = mergeTwoLists(l1->next, l2);
            return tmp;
        }
    }
};

leetcode #206. Reverse Linked List 反转列表
思路：一般链表的题目都会约束不能对链表的值进行操作，只能对链表的结点进行操作。处理链表问题，需要多用几个指针来存储结点信息。

leetcode206

在链表中，一旦访问链表中的某一个域，一定要保证这个域不为空，为了避免这个问题，可以在刚开始的判断一下该链表是否为空。

Solution:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur!= NULL){
            ListNode* next = cur->next;

            cur->next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
};

leetcode #92. Reverse Linked List II 翻转链表中指定区间的结点
一定要画图！题目要求one-pass，所以遍历的时候要保存四个结点：m前一个node, 第m个node, 第n个node,第n+1个node;

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == NULL or head->next == NULL)
            return head;
            
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode *pre = dummyHead;
        ListNode *cur = head;
        int pos = 1;
        while (pos < m) {
            pre = cur;
            cur = cur->next;
            ++pos;
        }
        ListNode *preNode = pre; //m-1 node
        ListNode *curNode = cur; //m node
        
        // cur -> Node_m
        while (pos <= n) {
            ListNode *next = cur->next; 
            cur->next = pre;
            pre = cur;
            cur = next;
            ++pos;
        }
        preNode->next = pre; // m - 1 -> n
        curNode->next = cur; // m -> n + 1
        return dummyHead->next;
    }  
};

leetcode #83. Remove Duplicates from Sorted List 删除链表中重复元素
无非就是在遍历的时候，用三个指针来保存结点：previous, current, next;

class Solution {
public:
    
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* pre = head;
        ListNode* cur = pre->next;
        
        while(cur != NULL)
        {
            if(cur->val == pre->val)
            {
                
                if(cur->next == NULL)
                {
                    
                    pre->next = cur->next;
                    return head;
                }
                else
                {
                    cur = cur->next;
                    pre->next = cur;
                }
            }
            else
            {
                pre = cur;
                cur = cur->next;
            }
        }
        return head;
    }
};

leetcode #2. Add Two Numbers 相加，再存入链表中
这题不能用一个整数来保存然后再相加，因为会出现溢出的情况；下面的答案是逐位相加，将进位保存

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *head = new ListNode(0);
        ListNode *cur = head;
        
        int extra = 0;
        while(l1 || l2 || extra)
        {
            int sum = (l1?l1->val:0) + (l2?l2->val:0) + extra;
            extra = sum/10;
            l1 = l1?l1->next:l1;
            l2 = l2?l2->next:l2;
            cur->next = new ListNode(sum%10);
            cur = cur->next;
            cout<<sum<<endl;
        }
        return head->next;
    }
};

leetcode #445. Add Two Numbers II
和#2题类似，但是难了很多。如果把链表翻转之后，就转换成了2，把加完之后的链表再翻转就是想要的答案了。所以该题是83和2的结合。

class Solution {
public:
    ListNode* reverse(ListNode* head)
    {
        ListNode* pre = NULL;
        ListNode* cur = head;
        if(cur == NULL) return head;
        while(cur != NULL) {
            ListNode* next = cur->next;
            
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    
    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        
        ListNode head(0);
        ListNode* cur = &head;
        int extra = 0;
        
        while(l1 || l2 || extra){
            
            int sum = (l1?l1->val:0 )+(l2?l2->val:0) + extra;
            extra = sum/10;
            l1 = l1?l1->next:0;
            l2 = l2?l2->next:0;
            cur->next = new ListNode(sum%10);
            cur = cur->next;
        }
        cur = reverse(head.next);
        return cur;
    }
};

leetcode #237. Delete Node in a Linked ListDelete Node in a Linked List 删除指定结点
注意本题是删除指定节点，而不是指定值
思路：由于指定节点前一个节点无法得到，所以就将下一个元素的值覆盖该节点，然后将下一个节点删除。一般情况下，我们对链表操作时，都不改变节点的值，只对节点本身操作。但是这题是特殊情况，所以链表问题不一定都是穿针引线的题
易错点：要考虑删除节点的下一个节点为空的情况，这种情况直接删掉该元素就可以了。

class Solution {
public:
    void deleteNode(ListNode* node) {
        if(node == NULL) return;
        if(node->next == NULL) {
            delete node;
            return;
        }
        node->val = node->next->val;
        
        ListNode* delNode = node->next;
        node->next = delNode->next;
        delete delNode;
        return;
        
    }
};

leetcode #328. Odd Even Linked List 奇偶链表

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        if(head->next->next == NULL) return head;
        ListNode* preOdd = head;
        ListNode* preEven = head->next;
        ListNode* odd = head->next->next;
       
        //目前肯定有>=3个节点
        ListNode* even = head->next->next->next;
        preOdd->next = odd;
        odd->next = preEven;
        
        preEven->next = even;
        if(preEven->next == NULL){
            return preOdd;
        }
        
        //目前肯定有4个节点;
        int i = 1;

        ListNode* cur = even->next; //第5个节点
        
        while(cur != NULL)
        {
            if(i%2 != 0)
            {
                
                odd->next = cur;
                cur = cur->next;
                odd = odd->next;
                odd->next = preEven;
                
            }
            else
            {
                even->next = cur;
                cur = cur->next;
                even = even->next;
                even->next = NULL;
            }
            i++;
        }
        
        even->next = NULL;
        return preOdd;
    }
};

leetcode #19. Remove Nth Node From End of List 删除倒数第n个结点
删除指定倒数第n个元素
思路：解法1）就是two-pass;第一遍遍历链表长度，第二遍删除元素
解法2）保存p节点和q节点，p和q之间对节点数刚好为n，相当于一个滑动窗口，不断往后移动，直到q节点移动到空节点时，这时p节点指向的节点时倒数n个节点的前一个节点
易错点：弄清题目中的n是从0开始还是从1开始算的；在这题中n是从1开始数，并且n是合法的

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        
        ListNode* p = dummyHead;
        ListNode* cur = head;
        while(n--)
        {
            cur = cur->next;
        }
        ListNode* q = cur;
        while(q != NULL)
        {
            p = p->next;
            q = q->next;
        }
        
        ListNode* delNode = p->next;
        p->next = delNode->next;
        delete delNode;
        return dummyHead->next;
    }
};

链表 leetcode题目总结 c++

链表

相关题目

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

二叉树之下