反转链表(C++非递归)_反转链表 三指针 c

方法一：直接将链表转换方向

 需要三个指针，分别为prev,cur,next。prev作用在于能使链表在连接的时候找到前一个结点，而next作用在于为链表寻找下一个节点。

反转过程：让当前节点的下一个位置指向原来链表中前一个结点，也就实现了链表的“箭头”方向转换，之后的每个结点以此类推。

迭代过程：让prev走到cur的位置上，cur走到next的位置上，next走到下一个next的位置上，值得注意的是，如果next已经为空了，则不能继续往下走，否则会出现野指针的出现。cur是空指针的时候，迭代过程结束。返回prev，也就是链表头。

特殊情况：当链表为空时，则无需操作，直接返回NULL即可。

代码如下：

* 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* prev,*cur,*next;
             if(head==NULL) return NULL;
              prev=NULL;
              cur=head;
              next=cur->next;
 
 
              while(cur)
              {
                  cur->next=prev;
 
                  prev=cur;
                  cur-next;
                  if(next) next=next->next;
              }
              return prev;
    }
};

方法二：头插法

创建一个新链表，将每个结点进行头插，得到的新链表就是反转后的链表。

需要两个指针cur和next。cur记录当前结点，next记录下一个结点位置。将cur的下一个指向newhead的位置（newhead是新链表的头部），然后把newhead更新为cur,再将cur的值更新为next，当cur为空指针时循环结束，也就不会再让next继续往下走，造成野指针的出现。返回newhead作为新链表的头节点。

代码如下：

 
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            ListNode* newhead = NULL;
            ListNode* cur = head;
            while (cur)
            {
                ListNode* next = cur->next;
                cur->next = newhead;
                newhead = cur;
                cur = next;
            }
            return newhead;
        }
    };

不开辟新节点的方法如下：

//头插法翻转链表(不创建新节点，需要用到一个尾指针)
template<typename datatype>
void linklist<datatype>::reverse_list2()
{
    listnode<datatype>* tail = head->next;
    listnode<datatype>* cur = head->next->next;
    while (cur)
    {
        tail->next = cur->next;
        cur->next = head->next;
        head->next = cur;
        cur = tail->next;
    }
}