您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

反转链表(迭代/双指针)

 我们要想反转链表,我想的是从最后一个元素开始把每个元素指向它的下一个元素,即一个一个改变元素的指向

/**
 * 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 *fir=head;//存储第一个元素地址
        ListNode *p=head;
        if(!head)//链表为0单独考虑
        {
            return 0;
        }
        while(p->next!=nullptr)//得到最后一个结点的地址
        {
            p=p->next;
        }
        head=p;//将头结点变成那最后一个结点
        while(p!=fir)
        {
            for(ListNode *find=fir;find;find=find->next)//一个一个结点找,直到找到一个结点的next指向最后一个结点(会改变)
            {
                if(find->next==p)
                {
                    p->next=find;//将最后一个结点的next指向找到的结点(会改变)
                    p=find;//注意这里将p变为那个我们找到的结点(即我们接着找指向它的结点)
                    break;
                }
            }
        }
        p->next=nullptr;//最后要将尾巴指向NULL
        return head; 
    }
};

该方法容易理解,不过效率不高

下面介绍另外一种做法——双指针做法(事实上,链表大部分时候都可以结合双指针)

  1. 定义两个指针: slow和 fast;slow在前 fast 在后。
  2. 每次让 fast的 next指向 slow,实现一次局部反转
  3. 局部反转完成之后,slow和 fast同时往前移动一个位置
  4. 循环上述过程,直至 fast到达链表尾部
/**
 * 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 *slow=nullptr;//前指针
        ListNode *fast=head;//后指针
        while(fast)
        {
            ListNode *temp=fast->next;
            fast->next=slow;//后指针指向前指针
            slow=fast;//
            fast=temp;//两个指针同时前移一格
        }
        return slow;
    }
};

该双指针的思路来自这里【反转链表】:双指针,递归,妖魔化的双指针 - 反转链表 


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进