【链表专题】剑指 Offer 24. 反转链表-跟着帅地玩副业，开拓第二曲线PlayOffer

lucca 普通 2022年12月30日上午1:59

原地颠倒

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head, p = head;
        while (p != null) {
            // 记录当前节点
            cur = p;
            // 保持调用链
            p = p.next;
            // 颠倒指针
            cur.next = pre;
            // 为下一次循环准备
            pre = cur;
        }
        return pre;
    }
}

头插法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = new ListNode();
        ListNode p = head, cur = p;
        while (p != null) {
            // 记录当前节点
            cur = p;
            // 保持调用链
            p = p.next;
            // 头插
            cur.next = node.next;
            node.next = cur;
        }
        return node.next;
    }
}

递归法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode next = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return next;
    }
}

0 赞同 0 条回复

糖鑫普通 2022年12月2日下午11:34

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    //迭代递归两种方法，此为迭代
    public ListNode reverseList(ListNode head) {
        ListNode cur=head;
        ListNode prev=null;
        ListNode tmp;
        while(cur!=null){
            tmp=cur.next;
            cur.next=prev;
            prev=cur;
            cur=tmp;
        }
        return prev;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2022年11月21日上午12:43

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        stack = []
        # 链表元素进入栈中 考虑特殊情况
        if not head:
            return head

        stack = []
        while head:
            stack.append(head)          # 把元素放进数组
            head = head.next
        stack = list(reversed(stack))

        for i in range(len(stack) - 1):
            stack[i].next = stack[i + 1]    # 根据反取得数组顺序重新构建链表
        stack[-1].next = None               # 最后一个节点就是反转前得头节点，一定给要next为空，否则是环
        return stack[0]

时间复杂度On
空间复杂度On

0 赞同 0 条回复

PatNick 普通 2022年11月19日上午9:23

class ListNode:
    def __init__(self,x):
        self.val = x
        self.next = None


def reverseList(head:ListNode)->ListNode:
    '''
    原地反转
    时间复杂度：O(N)
    额外空间复杂度 O(1)
    Args:
        head:

    Returns:

    '''
    if not head or not head.next:
        return head

    before = None
    cur = head

    # 这里必须多一个指针记录下一个节点，因为当cur进行就地反转后就无法知道后面的节点，需要提前记录
    after = head.next

    # 当after为None是说明cur已经到达结尾了
    while after:
        cur.next = before
        before =cur
        cur = after
        after = after.next

    # 做最后一次反转
    cur.next = before
    return cur

def reverseList1(head:ListNode)->ListNode:
    '''
    递归反转（直接超时了）
    Args:
        head:

    Returns:


    '''
    if not head or not head.next:
        return head
    # 反转子链表
    # 一层一层的递归就是要找到反转后的头节点（这个头节点在递归返回的过程并没有参与运算）
    re = reverseList1(head.next)
    # 在递归到最深层找到头节点后，在递归返回到过程中就需要进行每个节点到反转
    # 每一层的next节点就是下一层的头节点，而每一层的head和head.next的节点都是已知的，要做的反转就是将head.next的next反转为head，并将原来的head.next断开（不然就会出现死循环）
    head.next.next = head
    head.next = None

    return re

0 赞同 0 条回复

-辰华- 永久会员 2022年11月6日下午8:25

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {//递归
        if(head == null || head.next == null) return head;//头节点为空或头节点下一节点为空（只有1个节点）
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

时间复杂度、空间复杂度均为：O(n)

0 赞同 0 条回复

hmmm 普通 2022年11月1日下午8:09

“`c++
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head)
return NULL;
ListNode*p = head;
p = p->next;
head->next = NULL;
// 头插法创建链表
ListNode*q = p;
while(p!=NULL)
{
p = p->next;
q->next = head;
head = q;
q = p;
}
return head;
}
};“`
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

小趴菜永久会员 2022年11月1日上午12:05

时间o（n），空间o（1）
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while( cur!=null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}

0 赞同 0 条回复

长青普通 2022年10月29日下午3:53

#时间复杂度 o(N)
#空间复杂度o(1)

“`java
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode cur=head,pre=null;
while(cur!=null){
ListNode temp= cur.next;
cur.next=pre;
pre=cur;
cur= temp;

        }

         return pre;

}

0 赞同 0 条回复

韩杰普通 2022年10月28日下午9:30

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head,pre = null,temp;
        while(cur!=null){
            temp = cur.next;//临时节点指向下一个节点
            cur.next = pre;//当前节点改变指向
            pre = cur;//pre改为当前节点，也就是下一次的被指向节点
            cur = temp;//改变为链表的下一个节点，也就是下一个要被反转的节点

        }
        return pre;
    }
}

0 赞同 0 条回复

叶页耶夜烨邺普通 2022年10月28日下午6:52

迭代

/**
 * 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) {
        ListNode* curr = head;
        ListNode* prev = nullptr;
        ListNode* nxt = nullptr;
        while(curr){
            nxt = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
};

递归

/**
 * 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 || !head->next) return head;
        ListNode* res = reverseList(head->next); 
        head->next->next = head;
        head->next = nullptr;
        return res;
    }
};

0 赞同 0 条回复

和普通 2022年10月28日下午1:14

public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){return head;}
        ListNode list=reverseList(head.next);//递归方法
        head.next.next=head;
        head.next=null;
        return list;
    }

0 赞同 0 条回复

lobort 普通 2022年10月26日下午10:08

class Solution {
    public ListNode reverseList(ListNode head) {
    //特殊情况 
        if(head == null || head.next == null){
            return head;
        }
        ListNode cur = head, pre = null;
        while (cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre =cur;
            cur = temp;
        }
        return pre;
    }    
}

0 赞同 0 条回复

阿白普通 2022年10月26日上午6:31

1、说实话，不会，看了帅地代码略知一些
2、时间复杂度O（n），空间复杂度O（n）

struct ListNode{
    ListNode *next;
    int val;
};

ListNode* reverseList(ListNode *head)
{
    if (head == nullptr || head->next == nullptr)
        return head;//空节点、单节点，直接返回

    ListNode *cur = head;
    ListNode *pre = nullptr;
    while ( cur != nullptr)
    {
        ListNode *temp = cur->next;// cur->temp
        cur->next = pre;//cur->pre
        pre = cur;//pre(cur)->pre
        cur = temp;//temp(cur)
    }
    return pre;
}

0 赞同 0 条回复

努力刷题普通 2022年10月26日上午5:01


class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre
时间复杂度：O(N)
额外空间复杂度 O(1)

递归
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        tmp = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return tmp
时间复杂度:O(n)
空间复杂度:O(n)

0 赞同 0 条回复

cute. 普通 2022年10月25日下午11:50

1.递归解决

var reverseList = function(head) {
    // 递归终止条件
    if(head == null || head.next == null)
    return head;
    // 先对子链表进行反转/递归到最后一个节点，再从后向前进行反转
    const pre = reverseList(head.next);
    // 反转
    head.next.next = head;
    // 断开原有指向，链表的最后节点指向null
    head.next = null;
    // 并返回反转之后的头结点
    return pre;
};

时间复杂度:O(n)
空间复杂度:O(n)
2.原地反转

var reverseList = function(head) {
    // 递归终止条件
    if(head == null || head.next == null)
    return head;
    let cur = head;
    let pre = null;
    while(cur != null) {
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
};

时间复杂度: O(n)
空间复杂度: O(1)

0 赞同 0 条回复

星河普通 2022年10月25日下午12:45

递推公式：F(node=1) = F(node=2) + 反转node=1和node=2
class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);    // 调用递归并返回
    }
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre; // 终止条件
        ListNode res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }
}
时间O(N)，空间O(N)
链表的递推的时间空间复杂度一样的吗？
树的递推的时间空间复杂度一个是N，一个是logN，固定的吗？

0 赞同 0 条回复

cxc 普通 2022年10月25日上午12:01

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null) {
//定义一个临时节点存放下一个
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;
    }
}

0 赞同 0 条回复

优秀市民普通 2022年10月24日下午10:26

迭代法

“`java
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head, pre = null;
while(cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;

}
“`
时间复杂度o(n)
空间复杂度o(1)

0 赞同 0 条回复

云雾里普通 2022年10月24日下午10:08

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
//栈
    public ListNode reverseList(ListNode head) {
       Stack stack = new Stack<ListNode>();
        while(head!=null){
            stack.push(head);
            head=head.next;
        }
        ListNode listNode = new ListNode(-1);
        ListNode temp=listNode;
        while(!stack.isEmpty()){
            ListNode pop = (ListNode)stack.pop();
             temp.next = pop;
             temp=pop;
             temp.next=null;
        }
        return listNode.next;
    }
}

0 赞同 0 条回复

lone。普通 2022年10月24日下午9:58

解法一：迭代，双指针

class Solution1 {
  public ListNode reverseList(ListNode head) {
      if (head == null) {
          return null;
      }
      ListNode cur = head;
      ListNode pre = null;
      while (cur != null) {
          //暂存下一节点
          ListNode temp = cur.next;
          //修改next引用指向
          cur.next = pre;
          //暂存cur
          pre = cur;
          //访问下一节点
          cur = temp;
      }
      return pre;
  }
}

时间复杂度：O(N) 遍历链表

空间复杂度：O(1) cur，pre使用额外空间

解法二：递归

class Solution2 {
  public ListNode reverseList(ListNode head) {
      if (head == null) {
          return null;
      }
      return recur(head, null);
  }

  ListNode recur(ListNode cur, ListNode pre) {
      if (cur == null) {
          //cur尾结点
          return pre;
      }
      //递归
      ListNode recur = recur(cur.next, cur);
      //修改next引用指引
      cur.next = pre;
      //返回翻转链表头节点
      return recur;
  }
}

时间复杂度：O(N) 遍历链表

空间复杂度：O(N) 递归深度N

0 赞同 0 条回复

乱世枭雄普通 2022年10月24日下午7:27

思路：原地反转
每次当前节点指向前一个结点之后当前节点和前一个结点同时右移

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

1 赞同 0 条回复

zjl 普通 2022年10月24日下午7:24

原地反转，时间复杂度O(n) 空间复杂度O(1)，多写了一个没用的node，不改了

    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode node = new ListNode();
        node.next = head;
        ListNode p1 = node;  
        ListNode p2 = p1.next;
        ListNode p3 = p2.next;
        p1.next = null;
        p2.next = null;
        while(p3!=null){
            ListNode p4 = p3.next;
            p3.next = p2;
            p2 = p3;
            p3 = p4;
        }
        return p2;
    }

0 赞同 0 条回复

晨渊普通 2022年10月24日下午6:57

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next ==NULL)
           return head;

        ListNode *cur=head, *pre =NULL;//pre初始为NULL
        while(cur!=NULL){
            ListNode *temp = cur->next; //缓存下一个节点地址
            cur->next = pre;   //每次修改指向关系
            pre = cur;
            cur = temp;
        }

        return pre;  //pre
    }
};

时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

Y7n05h 普通 2022年10月24日下午5:46

class Solution {
public:
    ListNode *reverse(ListNode *head) {
        if (!head->next) return head;
        auto *backup = head->next;
        auto *ret = reverse(backup);
        backup->next = head;
        head->next = nullptr;
        return ret;
    }
    ListNode *reverseList(ListNode *head) {
        if (!head) return nullptr;
        return reverse(head);
    }
};

时间：O(n)
空间：O(n)

0 赞同 0 条回复

虾仁猪心普通 2022年10月24日下午1:59

思路：
S1：用到两个指针pre指针指向前一个节点（最开始时pre初始化为null），cur指针指向当前节点，
S2：循环遍历链表，当cur没指向空值时，就执行步骤S3
S3：用一个临时节点t存储当前节点的下一个节点，当前节点（cur）指向前继节点（pre），然后pre指针指向下一个节点，cur指向临时节点t，直到cur指向空值跳出循环。
时间复杂度：O(n)
空间复杂度： O(n)

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

    }
}

0 赞同 0 条回复

忆霁昕永久会员 2022年10月24日下午1:55

递归时间O(n) 空间O(n)

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        //反转以head.next为头结点的链表 返回值为反转后链表的头结点
        ListNode newHead = reverseList(head.next);
        //画图理解
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

迭代头插法实现反转时间O(n) 空间O(1)

class Solution {
    public ListNode reverseList(ListNode head) {
        //头插法
        ListNode newHead = null;
        //遍历
        ListNode p = head;
        while (p != null) {
            ListNode tmp = p.next;
            p.next = newHead;
            newHead = p;
            p = tmp;
        }
        return newHead;
    }
}

0 赞同 0 条回复

刺猬普通 2022年10月24日下午12:31

原地反转：
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp;
        ListNode* H = nullptr;
        while(head != nullptr)
        {
            temp = head->next;
            head->next = H;
            H = head;
            head = temp;
        }
        return H;
    }
};
递归：
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr)
            return nullptr;
        if(head->next == nullptr)
            return head;
        ListNode* H = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return H;
    }
};

时间复杂度:O(N)
空间复杂度:O(1)

0 赞同 0 条回复

🚲南下普通 2022年10月24日上午10:57

复杂度：
时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* next = new ListNode(-1);

        while(cur!=nullptr){
            next = cur->next; //首先存储cur下一个节点
            cur->next = pre; //改变当前节点cur的指向
            pre = cur; //更新pre和cur的位置
            cur = next;
        }
        return pre;

    }
};

0 赞同 0 条回复

@ 普通 2022年10月24日上午9:54

原地反转，只要在回溯的时候让当前引用的下一个引用指向自己即可
非原地反正的话，我的思路是设3个指针，分别指向当前元素，以及的它的前一个和后一个元素，然后每次遍历。只要让当前的元素指向他的前一个元素，然后在让这三个指针总体往后移，不断持续这个过程即可

//原地
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)
            return null;

        if(head.next == null)
            return head;

        ListNode res = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return res;

    }
}

//非原地
class Solution {

    private ListNode pre;
    private ListNode cur;
    private ListNode next;

    public ListNode reverseList(ListNode head) {
        if (head == null) return null;

        cur = head;
        next = cur.next;

        while(next != null) {
            cur.next = pre;
            pre = cur;
            cur = next;
            next = cur.next;
        }

        cur.next = pre;

        return cur;
    }

}

0 赞同 0 条回复

cxxz 普通 2022年10月24日上午12:39

递归，将子任务交给递归，设置好base_case，假设此时链表中该节点的子链表翻转完成，那么此时只需要设置当前节点的next的next指向自己，自己的next 指向空即可。返回值始终都是最后一个节点，因为后续操作中对此无更改便一直顺着函数调用栈返回。最后返回该节点即是翻转后的头节点。

ListNode* reverseList(ListNode* head) { 
        if (head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode *temp = reverseList(head->next);
        head->next->next=head;
        head->next = nullptr;

        return temp;
    }

时间复杂度O(n)
空间复杂度（函数调用栈） O(n)

学习到的原地反转思路，发现和自己最开始想用在递归中的思路很像，不过没想清楚，借助第三个node通过直接赋值来访问自己的前驱节点。

ListNode* reverseList(ListNode* head) { 
        if (head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode *temp, *cur = head, *pre=nullptr;
        while (cur != nullptr){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

时间复杂度：O(N)
额外空间复杂度（需要多申请几个变量） O(1)

0 赞同 0 条回复

啊哈普通 2022年10月24日上午12:16

/**
 * 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) {

        ListNode* cur = head;
        ListNode* tail = NULL;

        while(cur != NULL)
        {
            ListNode* temp = cur->next;     //节点记录原链表的cur下一个节点地址
            cur->next = tail;   //使得cur当前next指向tail；
            tail = cur;     //tial 移到cur位置
            cur = temp;     //cur回到原链表的下一个位置
        }
        return tail;
    }
};

时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

xye 普通 2022年10月23日下午11:44

func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var pre *ListNode
    for head != nil {
        next := head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}

反转链表

0 赞同 0 条回复

庄重普通 2022年10月23日下午11:26

 //个人理解：递归是由果推因，果是函数的功能，因为实现函数的功能
 //比如此题的函数功能是反转链表，调用递归默认会解决子问题，所以只需考虑如何从子问题得到整个问题的结果
 //递归需要，这个问题能够通过同样的逻辑不断分解出子问题，直到不能被分解(即返回判断条件)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return NULL;
        if(head->next == NULL) return head;

        //对除头节点的子链表( 子问题 )进行递归反转
        ListNode* pTmp = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;       

        return pTmp;

    }
};
//时间复杂度O(n) n为链表长度
//空间复杂度O(n) n个递归空间

//原地反转链表
//类似于两个数的交换，借助辅助变量，不过对于链表来说，需要保存后驱节点
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return NULL;
        if(head->next == NULL) return head;
        
        ListNode* pCur = head;
        ListNode* pPre = NULL;
        ListNode* pTmp = head ;
        //进行反转，注意需要先对后驱节点进行保存
        for(; pCur != NULL;){
            pTmp = pTmp->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pTmp;
        }
        return pPre;
    }
};
//时间复杂度O(n) n为链表长度
//空间复杂度O(1) 只借助几个变量

0 赞同 0 条回复

Gg 普通 2022年10月23日下午11:21

 // 解法一：递归
class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归终止条件
        if(head == null || head.next == null){
            return head;
        }
        // 进入递归
        ListNode newHead = reverseList(head.next);
        // 当前层处理
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

 // 解法二：迭代
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        // 定义两指针
        ListNode newHead = head;
        ListNode pre = null;
        // 遍历链表，每一个都进行反转
        while(newHead.next != null){
            ListNode next = newHead.next;
            newHead.next = pre;
            pre = newHead;
            newHead = next;
        }
        newHead.next = pre;
        return newHead;

    }
}

0 赞同 0 条回复

感到自己好渺小普通 2022年10月23日下午10:56

1.原地反转
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //原地反转
        //原始链表: 1->2->3->4->5->null
        //反转: null<-1<-2<-3<-4<-5
        //需要三个指针: pre cur temp
        //pre和cur分别指向NULL和head,用来改变链表的方向，temp用来保存链表，防止链表断开后找不着剩余链表
        if(head==NULL)  //判断链表是否为空
        {
            return NULL;
        }
        ListNode *pre = NULL;  
        ListNode *cur = head; 
        ListNode *temp = NULL;  //保留原始链表，防止当cur->next = pre时，下一次找不到剩余链表
        while(cur!=NULL)  //因为cur和pre相差一个结点，当cur达到NULL时，pre达到了原始链表的最后一个结点，也就是反转链表的第一个结点。
        {
            temp = cur->next;   //保存链表
            cur->next = pre;    //反转链表
            pre = cur;          //让pre和cur分别往前前进一个结点，继续反转链表
            cur = temp;
        }
        return pre;
    }
};
2.递归
时间复杂度：O(n)
额外空间复杂度：O(n)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //1.递归出口
        //head == NULL 判断链表是否是空表
        //head -> next == NULL 是递归出口，当链表有一个结点时，这时不用反转,返回head
        if(head == NULL||head->next ==NULL)
        {
            return head;
        }
        ListNode *temp = reverseList(head->next);
        //将单链表分解成head所指的结点和除了head链表中剩下的结点                                
        //1->2->3->4->5
        //1 2->3->4->5->NULL    head->1   第一层
        //  2  3->4->5->NULL    head->2   第二层
        //     3  4->5->NULL    head->3   第三层
        //        4  5->NULL    head->4   第四层
        //           5  NULL    head->5   第五层
        //这时链表中只有一个结点5，return head
        //返回到第四层head->4
        //对第四层进行反转，head->next->next = head
        //让head指向的结点的下一个结点(head->next)的指针域(head->next->next)指向head，完成反转
        //让head(反转之后的尾节点)指向NULL，NULL<-4<-5
        //放回到第三层，依次类推，完成递归
        head->next->next = head;
        head->next = NULL;
        return temp;
    }
};

0 赞同 0 条回复

symbol 普通 2022年10月23日下午9:54

//原地翻转
func reverseList(head *ListNode) *ListNode {
    var p *ListNode
    cur := head
    for cur != nil{
        next := cur.Next
        cur.Next = p
        p = cur
        cur = next
    }
    return p
}

//递归
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil { //注意这里
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil //注意这里
    return newHead
}

时间复杂度：O(n)，其中 n是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 n是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n层。

0 赞同 0 条回复

如梦似歌普通 2022年10月23日下午9:53

        if(head == null || head.next == null){
            return head;
        }

        ListNode p = head;
        ListNode cur = head.next;
        ListNode temp; //记录cur的下一个节点
        while(cur != null){
            temp = cur.next;
            cur.next = p;
            p = cur;
            cur = temp;
        }
        //当cur指针为null时，说明p恰好指向原链表最后一个节点处
        head.next = null;
        head = p;
        return head;

时间复杂度: O(n)
空间复杂度: O(1)

0 赞同 0 条回复

泡芙永久会员 2022年10月23日下午9:34

解法1：递归
思路：就是画图，先反转一个，后面直接递归
时间复杂度：O(N)
空间复杂度：O(N)

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode temp = reverseList(head.next);
        // 2 ——> 1
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

解法2：原地迭代
时间复杂度：O(N)
空间复杂度：O(1)

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        ListNode pre = null;

        while(cur != null) {
            // temp 保存后面的节点防止丢失
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

0 赞同 0 条回复

酥合普通 2022年10月23日下午8:38

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode ans = null;
        ListNode p = head;
        while(p != null){
            ListNode temp = p.next;
            p.next = ans;
            ans = p;
            p = temp;
        }
        return ans;
    }
}

时间复杂度: O(n)

0 赞同 0 条回复

Whatever 永久会员 2022年10月23日下午8:01

递归的思想，视后序要反转的节点为一个整体，改变指针指向并返回新的头结点，时间O(n)，空间O(n)

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = reverse(head);
        return newHead;
    }
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode temp = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

0 赞同 0 条回复

T 普通 2022年10月23日下午7:46

下面代码

    class Solution {
    public ListNode reverseList1(ListNode head) {
        ListNode cur = head , pre = null;
        // 迭代遍历
        while(cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    public ListNode recur(ListNode pre, ListNode cur) {
        if(cur == null) {
            return pre;
        }
        // 用来记录反转之后的头节点
        ListNode node = recur(cur, cur.next);
        cur.next = pre;
        return node;
    }

    public ListNode reverseList2(ListNode head) {
        if(head == null) return null;
        return recur(null, head);
    }
}

0 赞同 0 条回复

Ruby🗽 普通 2022年10月23日下午7:04

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode temp = head;
        ListNode newNode = null;
        while (temp != null){
            ListNode newNode1 = temp.next;
            temp.next = newNode;
            newNode = temp;
            temp = newNode1;
        }
        return newNode;
    }
}

时间复杂度n
空间复杂度 1

0 赞同 0 条回复

单个酒窝儿普通 2022年10月23日下午6:53

时间复杂度O(n) 空间复杂度O(1)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;
        ListNode *curr = head;
        while(curr != nullptr){
            ListNode *next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

0 赞同 0 条回复

Error 普通 2022年10月23日下午6:33

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        while head:
            tmp = head.next
            head.next = pre
            pre = head
            head = tmp
        return pre

时间复杂度 O(n)

0 赞同 0 条回复

绍熙普通 2022年10月23日下午5:34

class Solution {
    public ListNode reverseList(ListNode head) {
/*
        我们需要考虑F(n)和F(n-1)的关系，如果n代表以node为头节点的单向链表
        那么n-1就代表以node.next为头节点的单向链表
        令F(node.next)为问题：反转以node.next为头节点的单向链表
        那么，F(node)和F(node.next)之间的关系是?
        1 -> 2 -> 3
        那么，F(node=1)=F(node=2)+?
        这里假设子问题F(node=2)已经解决，那么我们如何解决F(node=1)：
        很明显，我们需要反转node=2和node=1， 即 node.next.next=node; 同时 node.next=null;
        所以，这个问题就可以是：F(node=1)=F(node=2)+ 反转node=2和node=1
        */
        // 递归出口:0或1个节点反转了就是本身
        if(head == null || head.next == null) {
            return head;
        }
        /*
        假设主函数实现的黑盒功能是:
        反转以head为头结点的链表,并让尾结点指空,同时返回反转后链表的头结点
        */
        // 反转head.next为头结点的链表并且让head.next.next指空,并返回head.next反转后的新的头结点
        ListNode res = reverseList(head.next);
        // 此时假设已经完成了head.next之后的反转:1->2<-3
        // 只需再将2->1即可完成反转,这个就是完成2->1的过程
        // 第一次执行head必定为1
        head.next.next = head;
        // 1指空的过程
        head.next = null;
        // 返回反转以head为偷的链表的头结点,其实也反转head.next的一样
        return res;
    }
}

0 赞同 0 条回复

just 普通 2022年10月23日下午5:27

//迭代方法iteration
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre=nullptr,* cur=head;
while(cur){
ListNode* temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;

};

0 赞同 0 条回复

追普通 2022年10月23日下午4:29

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;
        ListNode *curr = head;
        while(curr != nullptr){
            ListNode *next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

注意最后return的是哪个指针

0 赞同 0 条回复

Chin 普通 2022年10月23日下午4:06

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

迭代法
空间复杂度O1
时间复杂度On

0 赞同 0 条回复

晨普通 2022年10月23日下午4:02

class Solution(object):
    def reverseList(self, head):
    #     递归
    #     temp = self.reverseList(head.next)
    #     head.next.next =head
    #     head.next = None

    #     return temp

    #迭代
    #初始化，cur当前节点，pre为cur前节点
        cur = head
        pre = None

        while cur:
            # temp暂存cur后节点
            temp = cur.next
            #cur节点指向前节点
            cur.next = pre
            # 移动节点
            pre = cur
            cur  = temp
        return pre

时间复杂度O(n)
空间复杂度(1)

0 赞同 0 条回复

Haoyun 普通 2022年10月23日下午3:53

递归
时间复杂度：O(n)
空间复杂度：O(n)

var reverseList = function(head) {
   if(!head || !head.next) {
       return head;
   }
   const newHead = reverseList(head.next);
   head.next.next = head;
//断开之前的指针
   head.next = null;
   return newHead;
};

0 赞同 0 条回复

浅夏的无奈普通 2022年10月23日下午3:40

第一种：原地交换法

class Solution {
    ListNode A,B,C;
    public ListNode reverseList(ListNode head) {
        A=head;
        B=null;
        if(head==null||head.next==null){
            return head;
        }
       //利用两个辅助节点，把每一个节点的方向调换
       //用B收集其他节点
        while(A!=null){
             C=A.next;
            A.next = B;
            B=A;
            A=C;    
        }
        return B;
    }
}

第二种：递归

class Solution {
    public ListNode reverseList(ListNode head) {
        return res(head,null);
    }
    private ListNode res(ListNode fast,ListNode slow){
        if(fast==null){
            return slow;
        }
        ListNode res = res(fast.next,fast);
        fast.next=slow;

        return res;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年10月23日下午3:25

双指针，定义左右指针，右指针先指向头结点，作指针为空，定义一个新节点暂存右节点的下一个节点，让右指针指向左指针，
完成后，左右指针都向后移（把右指针赋给左指针，暂存节点的赋给右指针）完成后移直到右指针为null
时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode left = null;
        ListNode right = new ListNode(0);
        right = head;
        ListNode temp = new ListNode(0);
        while(right != null){
            temp = right.next;
            right.next = left;
            left = right;
            right = temp;
        }
        return left;
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年10月23日下午3:03

时间复杂度：O(n)
空间复杂度：O(n)
代码

ListNode reverseList2(ListNode head) {
        // 1. 递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 3. 等价关系式
        // reverseList(head.next)经过一系列指针操作变成reverseList(head)
        ListNode newList = reverseList2(head.next);

        ListNode node2 = head.next;
        node2.next = head;
        head.next = null;

        return newList;
    }

0 赞同 0 条回复

猫猫真可爱普通 2022年10月23日下午2:52

时间O(n) 空间O(1)

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode head2 = null;
         while (head != null){
            ListNode p = head.next;
            head.next = head2;
            head2 = head;
            head = p;
        }
        return head2;
    }
}

0 赞同 0 条回复

派大星普通 2022年10月23日下午12:18


class Solution {
//使用双指针来迭代
//时间复杂度O(n^2)
//空间复杂度O(1)
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode fastTemp = head;
        ListNode slowTemp = head;
        ListNode newList = new ListNode(0);
        ListNode temp = newList;
        while(slowTemp != null){
            if(fastTemp.next == null){
                temp.next = fastTemp;
                temp = temp.next;
                break;
            }else {
                while (fastTemp != null) {
                    if (fastTemp.next.next == null) {
                        temp.next = fastTemp.next;
                        temp = temp.next;
                        fastTemp.next = null;
                    }
                    fastTemp = fastTemp.next;
                }
                fastTemp = head;
            }
        }

        return newList.next;
    }
}

0 赞同 0 条回复

糖香香普通 2022年10月23日下午12:06

class Solution {
    public ListNode reverseList(ListNode head) {
        //双指针法
        //初始化
        ListNode cur = head, pre = null;
        while (cur != null) {
            ListNode temp = cur.next;   //暂存后继节点 cur.next
            cur.next = pre;     //修改next引用指向
            cur = temp;         //pre暂存cur
            pre = cur;          //cur访问下一节点
        }
        return pre;
    }
}

0 赞同 0 条回复

Asphyxia 普通 2022年10月23日上午11:36

来个递归版本的

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ret=NULL;
    void reverse(ListNode* pre,ListNode* now){
        if(now==NULL){
            ret = pre;
            return;
        }
        ListNode* temp = now->next;
        now->next = pre;
        reverse(now, temp);
        return;
    }
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pre=NULL;
        ListNode* nex=pHead;
        reverse(pre,nex);
        return ret;
    }
};

0 赞同 0 条回复

wxc 普通 2022年10月23日上午11:20

额

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        x1 = head
        x2 = None
        while(x1):
            x3 = x1.next
            x1.next = x2
            x2 = x1
            x1 = x3

        return x2

0 赞同 0 条回复

潜行1 我是火车王！普通 2022年10月23日上午10:43

递归

// 我最开始的解法
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil{
        return head
    }

    temp := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil

    return temp
}

0 赞同 0 条回复

mpweixin用户永久会员 2022年10月23日上午10:01

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode res=reverseList(head.next);
        head.next.next=head;
        head.next=null;    
        return res;
    }
}

时间复杂度O（n)
空间复杂度O（1）

0 赞同 0 条回复

你有点可爱喔普通 2022年10月23日上午9:33

时间复杂度O(n)
空间复杂度O(1)

    public ListNode reverseList(ListNode head) {
        if(head == null || head.next ==null){
            return head;
        }
        ListNode cur = head; // 当前的节点
        ListNode pre = null; // 前一个结点
        while(cur!=null){
            ListNode pNext= cur.next;//保存当前节点的下一个结点
            cur.next = pre;
            pre = cur;
            cur = pNext;
        }
        return pre;

    }

0 赞同 0 条回复

yanshuojune 普通 2022年10月23日上午1:11

方法1：迭代，通过保存curr.next 到temp，保证反转后后续节点不丢失，再反转，知道curr为空，此时的prev即为反转的结果
方法1时间复杂度：O(n)
方法1空间复杂度：O(1)
方法2：递归
方法2时间复杂度：O(n)
方法2空间复杂度：O(n)

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 迭代方法（原地反转）
        pre,curr = None,head
        while curr:
            temp = curr.next
            curr.next = pre
            pre = curr
            curr = temp
        return pre

        # 递归
        def recur(curr,pre):
            if not curr:
                return pre
            res = recur(curr.next,curr)
            curr.next = pre
            return res
        return recur(head,None)

1 赞同 0 条回复

黎昕普通 2022年10月23日上午12:21

// 模拟链表头插法调整钩链关系
时间复杂度：O(n)
空间复杂度：O(1)

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

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月22日下午11:39

原地反转

//原地反转
//时间O(n) 空间O(1)
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

使用辅助栈

//使用辅助栈
//时间复杂度O(n) 空间复杂度O(n)
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode cur = head;
        while(cur != null){
            stack.addLast(cur);
            cur = cur.next;
        }
        cur = stack.removeLast();
        ListNode ret = cur;
        while(stack.size() > 0){
            cur.next = stack.removeLast();
            cur = cur.next;
        }
        cur.next = null;
        return ret;
    }
}

递归

//递归
//时间复杂度O(n) 链表长度 空间复杂度(n) 系统栈
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        //递归就是模拟一次的操作
        //1.反转后序链表
        ListNode tmp = reverseList(head.next);//获得后序链表的头结点
        //2.head.next节点指向head
        head.next.next = head;
        //3.head指向null,避免成环
        head.next = null;
        return tmp;
    }
}

0 赞同 0 条回复

马啸天永久会员 2022年10月22日下午11:04

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

//recursive链表
class Solution2 {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode rev = reverseList(head.next);
        //(head.nex).next=head,又指了回来
        head.next.next = head;
        head.next = null;
        return rev;
    }
}

0 赞同 0 条回复

鸿渐普通 2022年10月22日下午10:33

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        //定义两个指针，一前一后，在原来的链表上进行操作
        ListNode pre = head;
        ListNode curr = head.next;
        ListNode temp;
        //将一开始的前一个指针指向空
        pre.next=null;
        while(curr!=null){
            //要修改curr的指向，这时先拷贝一份
            temp=curr.next;
            curr.next=pre;
            //更新指针的位置
            pre = curr;
            curr=temp;
        }
        return pre;
    }
}

0 赞同 0 条回复

宁永久会员 2022年10月22日下午10:24

递归与原地反转

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归
        /*
        if(head == null || head.next == null)
            return head;
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
        */
        //原地反转
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

0 赞同 0 条回复

狗蛋儿普通 2022年10月22日下午9:51

就是注意反转的时候的前后反转的顺序关系，和交换函数差不多

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = nullptr;
        ListNode *cur = pHead;
        ListNode *tmp = nullptr;
        while(cur){
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return  pre;
    }
};

0 赞同 0 条回复

Spermalow 普通 2022年10月22日下午9:39

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边界判断返回
        if (!head || !head->next) return head;
        // 翻转子列表
        ListNode * temp = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;

        return temp;
    }
};

0 赞同 0 条回复

波波_1936 普通 2022年10月22日下午9:37

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode pre = null;
        ListNode cu = head;
        ListNode next = null;
        while (cu != null) {
            next = cu.next;
            cu.next = pre;
            pre = cu;
            cu = next;
        }
        return pre;
    }

时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

mpweixin用户普通 2022年10月22日下午9:36

// 手动调整前后节点的指向
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode l = head;
        ListNode r = head.next;
        ListNode rr;
        while(r.next != null){
            rr = r.next;
            r.next = l;
            l = r;
            r = rr;
        }
        head.next = null; 
        r.next = l;
        return r;
    }
}

// 时间复杂度: O(n)
// 空间复杂度: O(1)

0 赞同 0 条回复

王艺超普通 2022年10月22日下午9:28

递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        return reverse(head,NULL);
    }
private:
    ListNode* reverse(ListNode* cur,ListNode* pre)
    {
        if(cur == NULL) return pre;
        ListNode *temp = reverse(cur->next,cur);
        cur->next = pre;
        return temp;
    }

};

双指针法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        ListNode *cur = head;
        ListNode *pre = NULL;
        while(cur)
        {
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

0 赞同 0 条回复

易水寒永久会员 2022年10月22日下午9:22

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode tmp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tmp;
    }

}

0 赞同 0 条回复

青木普通 2022年10月22日下午9:15

//分别用pre，cur，next标记三个位置的节点，进行反转
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;
    }
}

//很遗憾忘记了，用node标记反转后的头结点，head则标记马上要反转的节点，再进行反转。
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return node;
    }
}

1 赞同 0 条回复

小肸永久会员 2022年10月22日下午9:06

思路一：原地反转。pre初始化为null，cur指向第一个要翻转的节点，让cur.next=pre就可以实现防止，为了翻转整个链表，需要一个临时节点temp保存cur的下一个节点，执行cur.next=pre后，需要让pre=cur，cur=temp来为翻转下一个节点做准备。时间复杂度O(N)，空间复杂度O(1)。给出代码。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            // temp存放下一个要翻转的节点
            ListNode temp = cur.next;
            // 当前节点指向前一个节点，实现翻转
            cur.next = pre;
            // pre指向当前节点，方便下一个节点翻转
            pre = cur;
            // cur移向下一个要翻转的节点
            cur = temp;
        }
        return pre;
    }
}

思路二：递归。想好递归处理的过程，注意递归终止条件。时间复杂度O(N)，空间复杂度O(N)。给出代码。

class Solution {
    public ListNode reverseList(ListNode head) {
        // 当前节点是null或者尾节点，就不用翻转，直接返回
        if (head == null || head.next == null) {
            return head;
        }
        // newNode就是已经翻转后的链表的尾节点
        ListNode newNode = reverseList(head.next);
        // 让当前节点的下一个节点的指针域指向当前节点，实现翻转
        head.next.next = head;
        // 让当前节点的指针域指向null，避免当前节点和下一个形成环
        head.next = null;
        // 返回已经翻转后的链表的尾节点
        return newNode;
    }
}

思路三：使用辅助栈。时间复杂度O(N)，空间复杂度O(N)。给出代码

class Solution {
    private Stack<ListNode> stack = new Stack<>();
    public ListNode reverseList(ListNode head) {
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        ListNode dummyNode = new ListNode(-1);
        ListNode cur = dummyNode;
        while (!stack.isEmpty()) {
            cur.next = stack.pop();
            cur = cur.next;
        }
        cur.next = null;
        return dummyNode.next;
    }
}

0 赞同 0 条回复

天然普通 2022年10月22日下午8:56

方法1 时间复杂度O(n)

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        lst = []
        t1 = head
        k1 = head
        while head != None:
            lst.append(head.val)
            head = head.next

        for i in range(len(lst)):
           t1.val = lst[-(i+1)]
           t1 = t1.next

        return k1


方法二：原地反转，看的题解思路，然后双指针实现O(n)
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        t =None
        h =None
        if head is None:
            return head
        while head.next != None:
            t = head.next
            head.next = h
            h = head
            head = t
        head.next = h

        return head

0 赞同 0 条回复

So 普通 2022年10月22日下午8:31

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head, pre = null;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

时间复杂度：O(n)，空间复杂度：O(1)

0 赞同 0 条回复

一只骆驼普通 2022年10月22日下午8:08

原地反转，时间空间都为O(n)

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

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月22日下午8:04

时间复杂度为O（n），空间复杂度O（1）

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
//关键的指针，确定最后的头节点
        ListNode  pre = null;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

使用递归，时间复杂度空间复杂度O（n）

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null||head.next == null) return head;
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        //这刚开始没写出来
        head.next = null;
        return temp;
    }
}

0 赞同 0 条回复

1ue1uekin8 普通 2022年10月22日下午7:48

时间O(n)

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

0 赞同 0 条回复

194分贝普通 2022年10月22日下午7:32

// 时间发复杂度O(n)，空间复杂度O(1)。


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

        // 0个或1个结点，直接返回
        if (pHead == nullptr || pHead->next == nullptr) {
            return pHead;
        }

        ListNode *cur = pHead, *pre = nullptr;
        while (cur) {
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;
    }
};

0 赞同 0 条回复

【链表专题】剑指 Offer 24. 反转链表

共以下 81 个回答

原地颠倒

头插法

递归法

就是注意反转的时候的前后反转的顺序关系，和交换函数差不多

# 回答此问题取消回复

【链表专题】剑指 Offer 24. 反转链表

共以下 81 个回答

原地颠倒

头插法

递归法

就是注意反转的时候的前后反转的顺序关系，和交换函数差不多

# 回答此问题 取消回复

# 回答此问题取消回复