LeetCode (206单链表反转)

目录

题目描述:

代码:

第一种:

第二种:

第三种:

第四种:

第五种:

主函数:

ListNode类:

题目描述:

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

代码:

第一种:

构造一个新链表,从旧链表依次拿到每一个节点,创建新节点添加到新链表的头部,最后返回新链表的头节点

  public ListNode reverseList1(ListNode o1) {
        ListNode n1 = null;
        ListNode p = o1;
        while (p != null) {
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }
        return n1;
    }

第二种:

构造一个新的链表,从旧链表的头部移除节点,添加到新链表的头部,与上一个方法的区别在于未提供节点外层的容器类,

public ListNode reverseList2(ListNode head) {
        List list1=new List(head);
        List list2=new List(null);
        while(true){
            ListNode first=list1.removeFirst();
            if(first==null)
                break;
            list2.addFirst(first);
        }
        return list2.head;
    }
    public class List{
        ListNode head;
        public List(ListNode head){
            this.head=head;
        }
        public void addFirst(ListNode first){
            first.next=head;
            head=first;
        }
        public ListNode removeFirst(){
            ListNode first=head;
            if(first!=null){
                head=first.next;
            }
            return first;
        }
    }

第三种:

递归

 public ListNode reverseList3(ListNode p) {
        if(p==null||p.next==null)
            return p;
        ListNode last=reverseList3(p.next);//p.next为5
        p.next.next=p;//假设p为4,p.next为5,那么p.next.next=p就是5.next=4
        p.next=null;//4.next=null
        return last;
    }

第四种:

从链表每次拿到第二个节点,将其从链表断开,插入头部,直到它为null结束

 public ListNode reverseList4(ListNode o1) {
        //1.空链表,2.一个元素
        if(o1==null||o1.next==null)
            return o1;
        ListNode o2=o1.next;
        ListNode n1=o1;
        while(o2!=null){
            o1.next=o2.next;//将其断开
            o2.next=n1;//插入头部
            n1=o2;//n1指向头部
            o2=o1.next;//o2指向下一个节点
        }
        return n1;
    }

第五种:

将链表分成两个部分,不断从链表2的头部往下插入链表1的头部,直到链表2为空结束

public ListNode reverseList(ListNode o1) {
        //1.空链表,2.一个元素
        if(o1==null||o1.next==null)
            return o1;
        ListNode n1=null;
        while(o1!=null){
            ListNode o2=o1.next;
            o1.next=n1;
            n1=o1;
            o1=o2;
        }
        return n1;
    }

主函数:

 public static void main(String[] args) {
        ListNode o5=new ListNode(5,null);
        ListNode o4=new ListNode(4,o5);
        ListNode o3=new ListNode(3,o4);
        ListNode o2=new ListNode(2,o3);
        ListNode o1=new ListNode(1,o2);
        System.out.println(o1);
        ListNode n1=new Test().reverseList(o1);
        System.out.println(n1);
    }

ListNode类:

package reverseList;

public class ListNode {
    //反转单向链表
    public int val;
    public ListNode next;
    public ListNode(int val, ListNode next){
        this.val = val;
        this.next = next;
    }

    public String toString(){
        StringBuilder sb=new StringBuilder();//创建一个 StringBuilder 对象，用于构建字符串。
        sb.append("[");
        ListNode p=this;//创建一个指向当前节点的指针，用于遍历链表
        while(p!=null){
            sb.append(p.val);
            if(p.next!=null){
                sb.append(",");
            }
            p=p.next;
        }
        sb.append("]");
        return sb.toString();//将 StringBuilder 对象转换为字符串，并返回该字符串。
    }
    public ListNode reverseList(ListNode o1) {
        ListNode n1 = null;
        ListNode p = o1;
        while (p != null) {
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }
        return n1;
    }
}