首页 > 试题广场 >

编程实现单链表的逆转函数

[编程题]编程实现单链表的逆转函数

热度指数：5146 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

实现单链表的逆转函数，输入一个链表，反转链表后，返回翻转之后的链表。

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

xiao_niu_

classSolution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* temp = pHead;
        ListNode* pre = NULL;
        while(temp != NULL){
            temp = pHead->next;
            pHead->next = pre;
            pre = pHead;
            pHead = temp;           
        }
        return pre;
    }
};

编辑于 2017-09-21 20:37:11 回复(0)

baymaxhuang

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode node = head.next;
        head.next = null;
        while(node != null) {
            ListNode nextNode = node.next;
            node.next = head;
            head = node;
            node = nextNode;
        }
        return head;
    }
}

发表于 2017-09-04 22:42:10 回复(1)

叶赫那拉坤

  剑指offer原题 
  classSolution { 
  public: 
      ListNode* ReverseList(ListNode* pHead) { 
          ListNode* newHead=nullptr; 
          ListNode* current=pHead; 
          ListNode* pre=nullptr; 
          while(current){ 
              ListNode* next=current->next; 
              if(next==nullptr){ 
                  newHead=current; 
              } 
              current->next=pre; 
              pre=current; 
              current=next; 
          } 
          returnnewHead; 
      } 
  }; 
  
 

发表于 2017-09-02 09:28:44 回复(0)

元气の悟空

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead) return NULL;
        ListNode *p=pHead,*temp;
        ListNode *Head=(ListNode *)malloc(sizeof(ListNode));
        Head->next=NULL;
        while(p) 
            temp=p->next,p->next=Head->next,
            Head->next=p,p=temp;
        return Head->next;
    }
};

发表于 2017-11-09 18:21:15 回复(0)

牛客37569880号

建立一个有头结点和尾节点的结构体定义一个指针指向头结点指向的结点建立一个while循环退出条件位当尾结点等于定义的那个指针所指向的结点指向尾结点的指空尾结点的下一个指向头结点然后把尾结点赋给头结点然后把指空的结点赋给尾结点

发表于 2022-08-03 20:11:45 回复(0)

Java

凌晨两点敲代码

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode temp=null;
        ListNode pre=null;
        
        while(head!=null){
            temp=head.next;
            head.next=pre;
            pre=head;
            head = temp;
        }
        return pre;
    }
}

发表于 2021-09-04 22:48:48 回复(0)

风训

/*
只需要完成逆置链表函数
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/

//主要思路：利用栈对链表输出进行保存，同时，将栈的结果输出为链表中结点的值
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead)
            return nullptr;
        stack <int> s;
        ListNode *p =pHead;
        while(p){
            s.push(p->val);
            p=p->next;
        }
        ListNode *q =pHead;
        while(!s.empty()){
            q->val=s.top();
            s.pop();
            q=q->next;
        }
        return pHead;
    }
};

发表于 2020-06-23 10:50:45 回复(0)

C/C++

wydxry

/*
只需要完成逆置链表函数
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};
*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr) return pHead;
        ListNode *tmp,*cur=pHead,*pre=nullptr;
        while(cur){
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};

发表于 2020-04-10 00:23:09 回复(0)

AI大白菜

class Solution {
public:
    ListNode * ReverseList(ListNode* pHead) {

        //新建一个头结点
        ListNode * pHeader =(ListNode*) malloc(sizeof(struct ListNode));
        ListNode * pTail = pHeader;//新建尾结点,方便尾***r />         //第一个数据点
        ListNode *current = pHead;
        stack<int> s;
        while (current!=NULL)
        {
            //将每个结点的数据域入栈
            s.push(current->val);
            current = current->next;
        }
        while (!s.empty())
        {
            int value = s.top();//栈的头结点的数据弹出，也就是链表最后一个结点的数据域弹出
            s.pop();
            //新建一个结点
            ListNode* newnode = (ListNode*)malloc(sizeof(struct ListNode));
            newnode->val = value;
            newnode->next = NULL;
            //尾***r />             pTail->next = newnode;
            pTail = newnode;

        }
        return pHeader;

    }
};

发表于 2020-03-24 23:11:18 回复(0)

Java

littleshan

public class Solution {
    ListNode root, tp = new ListNode(0);
    public ListNode ReverseList(ListNode head) {
        root = tp;
        dfs(head);
        tp.next = null;
        return root.next;
    }
    public void dfs(ListNode head) {
        if(head != null) {
            dfs(head.next);
            tp.next = head;
            tp = tp.next;
        }
    }
}

发表于 2020-03-13 20:48:18 回复(0)

hash1729

一次遍历即可，只改变next指针

发表于 2020-03-02 20:47:54 回复(0)

bingzibing

public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre=null;//指向当前节点的前驱
ListNode next=null;//指向当前节点的后继
while(head!=null){
next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
}
}

发表于 2019-10-08 09:43:28 回复(0)

刘诗歌

时间复杂度O(n)

class Solution {   
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead || !pHead->next)
            return pHead;
        if(!pHead->next->next)
        {
            pHead->next->next = pHead;
            pHead = NULL;
            return pHead->next;
        }
        ListNode* pre = pHead;
        ListNode* p = pHead->next;
        ListNode* post = p->next;
        pre->next = NULL;
        while(post)
        {
            p->next = pre;
            pre = p;
            p = post;
            post = post->next;
        }
        p->next = pre;
        return p;
    }
};

发表于 2019-10-05 21:44:41 回复(0)

Java

蹲在厕所里数大尾巴蛆

public ListNode ReverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode pre = null, next = null;
    while (head.next != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    head.next = pre;
    return head;
}

发表于 2019-10-05 19:52:29 回复(0)

Iceman96

通过一次遍历得到链表的长度len，然后根据链表长度len来确定后续遍历的次数，每取出一个元素len-1

 public ListNode ReverseList(ListNode head) {
        if (head == null)
            return null;
       ListNode temp = head;
        ListNode res = new ListNode(0);
            int len = 0;
            while (temp.next != null){
                temp = temp.next;
                len++;
            }
            res.val = temp.val;
            ListNode result = res;
            while (len > 0){
                temp = head;
                for (int i = 0; i < len-1; i++ ){
                    temp = temp.next;
                }
                res.next = new ListNode(temp.val);
                res = res.next;
                len--;
            }
        return result;
    }

发表于 2019-09-09 20:52:29 回复(0)

那你拉紧我啊

public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}

}

发表于 2019-08-21 12:40:01 回复(0)

Java

努力做一个体面人

public ListNode ReverseList(ListNode head) {
if(head == null||head.next == null) return head;
ListNode pre = null;
ListNode cur = head;
while(head!=null){
cur = head;
head = head.next;
cur.next = pre;
pre = cur;
}
return pre;
}
迭代法，很简单

发表于 2019-07-07 20:49:52 回复(0)

我的天鸭

/*
只需要完成逆置链表函数
struct ListNode {     int val;     struct ListNode *next;     ListNode(int x) :             val(x), next(NULL) {     }
};
*/
//依次遍历链表节点，每遍历一个节点就逆置一个节点
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead)
            return nullptr;
        ListNode* pHeadNew = nullptr;
        while(pHead)
        {
            ListNode* pTemp = pHead->next;
            pHead->next = pHeadNew;
            pHeadNew = pHead;
            pHead = pTemp;
        }
        return pHeadNew;
    }
};

发表于 2019-06-24 14:38:49 回复(0)

C/C++

~似曾相识燕归来

/*
只需要完成逆置链表函数
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    /**
    * 每次从旧链表的头部取出节点插入到新链表中
    */
    ListNode* ReverseList(ListNode* pHead) {
        if (nullptr == pHead || nullptr == pHead->next) {
            return pHead;
        }

        ListNode *pNewHead = nullptr;
        ListNode *pTemp = nullptr;
        while (pHead) {
            pTemp = pHead;
            pHead = pHead->next;

            // 头插法
            pTemp->next = pNewHead;
            pNewHead = pTemp;
        }
        return pNewHead;
    }
};

发表于 2019-05-07 10:36:40 回复(0)

牛客6854564号

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead==NULL||pHead->next==NULL)
            return pHead;
        ListNode *p,*newHead,*oldHead;
        for (oldHead=pHead->next,newHead=pHead;oldHead!=NULL;)
        {
            p=oldHead;
            oldHead=oldHead->next;
            p->next=newHead;
            if (newHead==pHead)
                newHead->next=NULL;
            newHead=p;
        }
        return newHead;
        
    }
};

编辑于 2018-04-23 15:58:06 回复(0)