15 图解剑指Offer 反转链表 Java题解

淩亂°似流年 2023-02-20 12:21 6阅读 0赞

### 15 图解剑指Offer 反转链表 Java题解 ###

*  15 图解剑指Offer 反转链表 Java题解
 *   *   *  题目链接
         *  题目描述
         *  题解:
         *  图解:
         *  代码:
         *  复杂度

# 15 图解剑指Offer 反转链表 Java题解 #

### [题目链接][Link 1] ###

### 题目描述 ###

输入一个链表，反转链表后，输出新链表的表头。

### 题解: ###

1.首先判断头节点是否为null ，如果为null，则返回null  
2.如果只有一个节点，返回head。  
3.创建三个指针 pre cur temp，当cur不为null时，temp用来存放cur.next，然后再把cur.next指向pre，最后pre ，cur都像后挪动一位。pre = cur，cur = cur.next  
4.最后返回pre

### 图解: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]

### 代码: ###

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode FindKthToTail(ListNode head,int k) { 
            if(head ==  null) return null;
            ListNode tempHead = head;
            int len = 0;
            while(tempHead != null) { 
                tempHead = tempHead.next;
                len++;
            }
            if(k > len || k == 0) { 
                return null;
            }
            
            ListNode prev = head;
            ListNode after = head;
            for(int i = 1; i < k; i++) { 
                prev = prev.next;
            }
            while(prev.next != null) { 
                prev = prev.next;
                after = after.next;
            }
            
            return after;
        }
    }

### 复杂度 ###

空间复杂度: 空间复杂度为O(1)  
最坏时间复杂度: 遍历时间复杂度O( n)

[Link 1]: https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200626231457212.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70