1.递归法:时间复杂度O(n)
递归的时间复杂度一般看层数,这个层数是n层,每层执行一次操作,所以是O(n)
/*
原理:把后半部分看成已经反转好的数据
*/
public ListNode reverseAdjoinList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode nextNode = head.next;
head.next = reverseAdjoinList(head.next.next);
nextNode.next = head;
return nextNode;
}
2.遍历法:时间复杂度O(n)
/*
原理:由于两个数的反转会影响到三个数的位置,还包括一个前继,所以需要用到四个变量
*/
public ListNode reverseAdjoinList(ListNode head) {
ListNode curr = head;
ListNode nextNode,nextNextNode;
ListNode realHead = new ListNode();
realHead.next = head;
ListNode pre = realHead;
while (curr != null && curr.next != null){
nextNode = curr.next;
nextNextNode = curr.next.next;
pre.next = nextNode;
nextNode.next = curr;
curr.next = nextNextNode;
pre = curr;
curr = nextNextNode;
}
return realHead.next;
}