[0206.翻转链表]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * pre = head;
        ListNode * cur = head->next;
        while(cur != NULL){
            ListNode * tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
       head->next = NULL;
       return pre;
    }
};
  • 控制台给的例子运行没问题 但提交上去说是什么null。o 原来是我没考虑head是个空指针的情况
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL)
            return head;
        ListNode * pre = head;
        ListNode * cur = head->next;
        while(cur != NULL){
            ListNode * tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
       head->next = NULL;
       return pre;
    }
};
  • 用C++就是比较顺手啊,主要本科学C++语言学得比java扎实,数据结构课程和算法分析课程都是C++语言,用的顺手了。结合自身实际再加上客观环境我发现还是C++适合我啊,跟一开始想的方向一致,努力叭 :)
 class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点,因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};
  • 还是随想录给的逻辑清楚 多看多写吧

[标准答案]

  • 双指针法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点,因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};
  • 递归法

递归法相对抽象一些,但是其实和双指针法是一样的逻辑,同样是当cur为空的时候循环结束,不断将cur指向pre的过程。

关键是初始化的地方,可能有的同学会不理解, 可以看到双指针法中初始化 cur = head,pre = NULL,在递归法中可以从如下代码看出初始化的逻辑也是一样的,只不过写法变了。

具体可以看代码(已经详细注释),双指针法写出来之后,理解如下递归写法就不难了,代码逻辑都是一样的。

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比,如下递归的写法,其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};

我们可以发现,上面的递归写法和双指针法实质上都是从前往后翻转指针指向,其实还有另外一种与双指针法不同思路的递归写法:从后往前翻转指针指向。

具体代码如下(带详细注释):

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        
        // 递归调用,翻转第二个节点开始往后的链表
        ListNode *last = reverseList(head->next);
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点,next 需要指向 NULL
        head->next = NULL;
        return last;
    }
}; 

[0024.两两交换链表中的节点]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL){
            return head;
        }
        ListNode* shead = new ListNode(0 , head);    
        ListNode* cur = shead;
        while(cur->next != nullptr && cur->next->next != nullptr)  {
            ListNode* temp1 = cur->next; 
            cur->next = cur->next->next;
            ListNode* temp2 = cur->next->next->next; 
            cur->next->next->next = temp1;
            temp1->next = temp2;
            cur = temp1->next;
        }   
        return head;
    }
};
  • 1.是中间变量设谁 不够清楚 2.是没有注意到 第二行按cur->next->next寻找时 其中要经过的cur->next已经改变了 不再是之前(第一行)那个cur->next路径了 也是就是说 按顺序执行代码时 上一行的赋值会影响下一条的赋值

    cur->next = cur->next->next;

    cur->next->next = temp1;

    cur->next->next->next = temp2;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) { 
        ListNode* shead = new ListNode(0 , head);    
        ListNode* cur = shead;
        while(cur->next != nullptr && cur->next->next != nullptr)  {
            ListNode* temp1 = cur->next; 
            ListNode* temp2 = cur->next->next->next; 
            cur->next = cur->next->next;
            cur->next->next = temp1; 
            cur->next->next->next = temp2;
            cur = cur->next->next;
        }   
        return head;
    }
};
  • 结果不对

    输入 [1,2,3,4] 输出[1,4,3] 预期结果[2,1,4,3]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) { 
        ListNode* shead = new ListNode(0 , head);    
        ListNode* cur = shead;
        while(cur->next != nullptr && cur->next->next != nullptr)  {
            ListNode* temp1 = cur->next; 
            ListNode* temp2 = cur->next->next->next; 
            cur->next = cur->next->next;
            cur->next->next = temp1; 
            cur->next->next->next = temp2;
            cur = cur->next->next;
        }   
        return shead->next; 
    }
};
  • 原因是因为最后return语句 不应该再是返回head 因为经过两两交换后 head指向的是第链表中二个元素 而不是第一个

[标准答案]

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head,这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位,准备下一轮交换
        }
        return dummyHead->next;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

原文地址:http://www.cnblogs.com/deservee/p/16852254.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性