反转链表-力扣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;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
