题目描述
输入一个链表，反转链表后，输出新链表的表头。
解题思路一 头插法
时间复杂度O(n)，空间复杂度O(n)
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode linkedList = new ListNode(0);//头插法
ListNode node = null;
while (head != null){
node = new ListNode(head.val);
node.next = linkedList.next;
linkedList.next = node;
head = head.next;
}
return linkedList.next;
}
解题思路二
这是牛客@伊万夫斯基的思路
815472960_1566642098849_C3B4D3532589FC2990420BCEA62A8DBF.jpg
public ListNode ReverseList2(ListNode head) {
if(head == null || head.next == null) //空链表或链表只有一个结点
return head;
ListNode pre = null; //前一个结点
ListNode next = null; //下一个结点
while (head != null){
//改变原有链表的指针指向
next = head.next;//记录下一个结点的位置，避免断链
head.next = pre; //当前结点指向前一个结点，实现反转
pre = head; //pre向后一位
head = next; //head向后一位
}
return pre;
}
