206. 反转链表 （精选）

2023-11-18

206. 反转链表 - 力扣（LeetCode）

思路：

注意leetcode是没有头节点的，只有数据节点

1 先将指针放到最后，然后从开头取节点，放到此节点后面 遍历2遍，不好

2 引入头节点，头插法 可以就用本来的链表 / 定义一个新的链表

3 原地反转链表的线

迭代（双指针）

递归 相当于1的思路

1简单，就没有代码了

2：

引入头节点的头插法（用本来链表）;

/**
 * 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) {
        //原地反转  双指针
        //递归
        //栈
        //引入头节点  头插法
 
 
        //引入头节点，头插法
 
        if(head==null || (head!=null && head.next==null)){
            return head;
        }
    
        ListNode l=new ListNode();
        l.next=head;
        
        ListNode now=head;
 
        while(now.next!=null){
            ListNode temp=now.next;
            now.next=now.next.next;
            temp.next=l.next;
            l.next=temp;
        }
 
        return l.next;
 
 
 
 
    }
}

定义新链表的头插法：

/**
 * 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) {
        //注意leetcode是没有头节点的，只有数据节点
 
        //1 先将指针放到最后，然后从开头取节点，放到此节点后面     遍历2遍，不好
        //2 引入头节点，头插法       可以就用本来的链表 /   定义一个新的链表
        //3 原地反转链表的线
            //迭代
            //递归  /   循环
        
        ListNode  l=new ListNode();
 
        ListNode now=head;
        ListNode t;
        while(now!=null){
            t=now.next;
            now.next=l.next;
            l.next=now;
            now=t;
        }
 
        return l.next;
 
 
 
    }
}

3：

递归：

/**
 * 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) {
        //注意leetcode是没有头节点的，只有数据节点
 
        //1 先将指针放到最后，然后从开头取节点，放到此节点后面     遍历2遍，不好
        //2 引入头节点，头插法       可以就用本来的链表 /   定义一个新的链表
        //3 原地反转链表的线
            //迭代
            //递归  /   循环
        
        
        //原地反转的递归写法        后面是反转完的，前面是待反转的，相当于先将指针指向最后
        if(head==null || head.next==null){
            return head;
        }
 
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
 
 
 
 
    }
}

迭代/双指针：

/**
 * 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) {
        //原地反转  双指针
        //递归
        //栈
        //引入头节点  头插法
 
 
        //双指针
        if(head==null || (head!=null && head.next==null)){
            return head;
        }
 
        ListNode pre=null;
        ListNode now=head;
 
        ListNode temp;
        while(true){
            temp=now.next;
            now.next=pre;
            pre=now;
            if(temp==null){
                break;
            }
            now=temp;
        }
        
        return now;
 
 
 
    }
}