算法训练第二期链表

15次阅读

共计 3278 个字符，预计需要花费 9 分钟才能阅读完成。

难度简单 54

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

 输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

思路一：

虽然是链表的练习，但是算法的思路非常多。依旧我之前所说会用到各种办法，不是链表部分只用链表

本题：需要返回一个链表指针，这是一个新的链表。这个新的链表本质上是从旧的链表尾一个一个拿元素。也就是对于旧的链表而言，实际上是一个先进后出的一个情形。所以我们首先想到符合这个特点的就是栈。

从头开始压栈，压完之后一个一个出栈。放入新的链表中；

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {if(head == NULL) return NULL;
        if(head->next == NULL) return head;
        stack<ListNode*> stack_listnode;
        while(head != NULL) {stack_listnode.push(head);
            head = head->next;
        }
        ListNode* q = stack_listnode.top();
        ListNode* qHead = q;
        stack_listnode.pop();
        while(stack_listnode.size() != 0) {q->next = stack_listnode.top();
            stack_listnode.pop();
            q = q->next;
        }
        q->next = NULL;
        return qHead;
    }
};

思路二：

如果你是一个认认真真学习过数据结构的同学，你一定会想到的一个思路：头插法和尾插法！

说到这里想必你已经明白了。头插和尾插会在另一个 md 里面详细说明；

思路三：

简单的来说，通过两个指针来在给定链表上爬，在爬的过程中给第三个指针赋值，慢慢将第三个指针构成新的链表。有点像 DNA 的转录过程….

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p1,*p2,*p3;
        p1 = NULL;
        p2 = head;
        while(p2!=NULL){
            p3 = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = p3;
        }
        return p1;
    }
};

难度简单 31

实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。

示例：

 输入：单向链表 a ->b->c->d->e->f 中的节点 c
结果：不返回任何数据，但该链表变为 a ->b->d->e->f

思路：

本题的关键是在于理解题意。

题意分析：

题目只给你某一个结点，其他什么都不给，链表你也拿不到。让你删除这个元素，个人认为这是一个很好的案例。我拿不到链表，只能拿到结点。也不知道这是第几个…

但是我们可以访问这个结点之后的结点，也可以访问之后的之后的结点。所以把本结点等于 next 的值，然后把 next 删掉，偷梁换柱。

怎么删除呢？其实就是把 node->next = node->next->next 直接赋值就行。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {if(node == NULL) return ;
        node->val = node->next->val; 
        node->next = node->next->next;
    }
};

难度简单 533

请判断一个链表是否为回文链表。

示例 1:

 输入: 1->2
输出: false

示例 2:

 输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路一：

放进数组一个一个比较

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {if(head == NULL)    return true;
        if(head->next == NULL)      return true;
        vector<int> array;
        int count = 0;
        while(head != NULL){array.push_back(head->val);
            head = head->next;
        }
        for(int i = 0;i < array.size() / 2; i++){if(array[i] != array[array.size() - i - 1])
                return false;
        }
        return true;
        
    }
};

思路二：

使用快慢指针，找到中间，把后半部分 reverse，从中间开始比较。

class Solution {
public:
    bool isPalindrome(ListNode* head) {//O(n)、O(1)
        ListNode* slow = head, *fast = head,  *prev = nullptr;
        while (fast){//find mid node
            slow = slow->next;
            fast = fast->next ? fast->next->next: fast->next;
        }
        while (slow){//reverse
            ListNode* temp = slow->next;
            slow->next = prev;
            prev = slow;
            slow = temp;
        }
        while (head && prev){//check
            if (head->val != prev->val){return false;}
            head = head->next;
            prev = prev->next;
        }
        return true;
    }
};

难度中等 23

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即 617 + 295
输出：2 -> 1 -> 9，即 912

进阶： 假设这些数位是正向存放的，请再做一遍。

示例：

 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即 617 + 295
输出：9 -> 1 -> 2，即 912

思路：

本题的思路很明确：链表的合并 + 进位问题。（链表的合并，会在链表专题中专门讲）

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *sum = l1;
        while(l1->next && l2->next)
        {
            l1->val += l2->val;
            l1 = l1->next;
            l2 = l2->next;
        }
        l1->val += l2->val;
        if(!l1->next)
        {l1->next = l2->next;}
        l1 = sum;
        while(l1->next)
        {if(l1->val >= 10)
            {
                l1->val -= 10;
                l1 = l1->next;
                l1->val++;
            }
            else
            {l1 = l1->next;}
        }
        if(l1->val >= 10)
        {
            l1->val -= 10;
            l1->next = new ListNode(1);
            return sum;  
        }
        else
        {return sum;}
    }       
};

正文完