程序员

[算法之链表]-反转单链表

2020-05-12  本文已影响0人  凡毓不凡
  • 链表是一种数据结构,应用在很多场景中,如 JDK1.8 中得HashMap,ConcurrentHashMap等集合类中
  • 本文旨在以通俗得方式讲解高频面试题:反转单链表
图片来自CSDN,若涉及到侵权,请联系作者删除
public class Solution{
    public ListNode  reverse(ListNode head){
        if(head==null || head.next==null)  return head;
        // p指的是反转之后得新链表
        ListNode p =null;
        // head得下一个节点
        ListNode q =null;    
        while(head!=null){
            q = head.next; // 始终保持head得下一个位置给q  (1)
            head.next = p; // 将head下一个节点得指针指向p(将head从原先得链表中剥离出去  (2))
            p = head;// 将head得位置给到p(将head替换为p  (3))
            head = q ; // 将q得位置给到head(又回到最初得链表结构,但是此时链表得头节点以及移到 另一个链表p上了  (3))
        }
        return p;
    }
}

@Data
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

时间复杂度:由于需要遍历整个链表来逆序,所以时间复杂度为 O(n)
空间复杂度:由于没有开辟额外得内存空间,所以空间复杂度为 O(1)

  1. ☛ 文章要是勘误或者知识点说的不正确,欢迎评论,毕竟这也是作者通过阅读源码获得的知识,难免会有疏忽!
  2. 要是感觉文章对你有所帮助,不妨点个关注,或者移驾看一下作者的其他文集,也都是干活多多哦,文章也在全力更新中。
  3. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处!
上一篇 下一篇

猜你喜欢

热点阅读