//题干链表定义
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
//方式一:递归方式
思路:假设链表为[1,2,3,4,5]先迭代到链表末尾5,然后从5开始依次反转整个链表
如下图所示,先迭代待最后一位5,并且设置一个新的节点newList作为反转后链表的头结点,由于整个链表反转后的头就是最后一个数,所以newList存放的一直是反转后的头结点的地址,将head指向的地址赋值给head->next->next指针,并且一定要记得让head->next =NULL,也就是断开现在指针的链接,否则新的链表形成了环,下一层head->next->next赋值的时候会覆盖后续的值。依次反转。。
代码:
public ListNode ReverseList(ListNode head) {
if (head==null || head.next ==null) //链表为空直接返回,而head->next为空是递归基
return head;
ListNode newList = ReverseList(head.next); //一直循环到链尾
head.next.next = head; //翻转链表的指向
head.next = null; //记得赋值NULL,防止链表错乱
return newList; //新链表头永远指向的是原链表的链尾
}
newList
//方式二:非递归方式
思路:根据下图,先给定一个空的链表newList,然后判断传入的链表head是不是空链表或者链表元素只有一个,如果是,直接返回就可以。如果不是,则对链表进行迭代,然后给一个临时变量temp存储head.next,然后改变head.next的指向newList,然后把head赋值给newList,接着让head等于临时变量temp,就这样一直迭代完整个链表,返回newList就可以
代码:
public ListNode ReverseList(ListNode head) {
ListNode newList = null;
if (head==null || head.next ==null)
return head;
while (head!=null){
ListNode temp = head.next;
head.next = newList;
newList = head;
head = temp;
}
return newList;
}