反转链表-力扣206

反转链表-力扣206

方法一

    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;
    }

方法二

  /*
    方法2     写了两个类库,运用了面向和对象的思想,创建建立和移除两个方法
与方法1类似,构造一个新链表,从旧链表头部移除节点,添加到新链表头部,完成后
新链表即是倒序的,区别在于原题目未提供节点外层的容器类,这里提供一个,另外一
个区别是并不去构造新节点
     */
public ListNode reverseList2(ListNode head){
    List list1=new List(head);
    List list2=new List(null);
    while (true){
        ListNode first=list1.reverseList();
        if(first==null){
            break;
        }
        list2.addFirst(first);
    }
return list2.head;
}
    static class List{
        ListNode head;

        public List(ListNode head){
            this.head=head;
        }
        public void addFirst(ListNode first){//头插法
            first.next=head;
            head=first;//更新变成first
        }
        public ListNode reverseList(){//返回头节点
            ListNode first=head;//找到头节点.第一个节点
            if(first!=null){
                head=first.next;//移走了,原来的就是第一个
            }
            return first;//返回的头节点
        }

    }

方法三

//方法三-递归
    /*
    1,2,3,4,5
     */

    public ListNode reverseList3(ListNode p){
        if(p==null||p.next==null){
            return p;
        }
        ListNode last=reverseList3(p.next);
        p.next.next=p;//  p  p.next  p.next.next->p
        p.next=null; // 4   5     5->4  4->null
        return last; //p指向的问题
    }

方法四

/*
方法四
n1
         o1
4->3->2->1->5->nul1
01d1
new1
*/
  public ListNode reverseList4(ListNode o1){
      ListNode o2=o1.next;
      ListNode n1=o1;
      while (o2!=null){
          o1.next=o2.next;//2   把第二个节点从链表中移出
          o2.next=n1;//3   旧链表的o2指向新链表n1,此时n1和o1同体

          n1=o2;//4    n1指向o2,n1和o2的值都一样,把链表头的位置让给o2
          o2=o1.next;//5  回归原来的位置
      }
      return n1;
  }

方法五

 //方法五
    /*
n1
5->4->3->2->1->nu11
*/
  public ListNode reverseList(ListNode o1){
      ListNode n1=null;     //新链表开始为空
      while (o1!=null){     //o1移动到的位置是最后一个,也就是为空的时候
          ListNode o2=o1.next;  //节点2是o1的下一个节点
          o1.next=n1;  //把o1移动到新链表的头部
          n1=o1;  //  o1就变成了n1
          o1=o2;   //o2的位置就是o1,指针复位
      }
      return n1;
  }

热门相关:亿万盛宠只为你   锦庭娇   神算大小姐   万古至尊   裙上之臣