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

• 链表是一种数据结构，应用在很多场景中，如 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. ☛ 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处！