剑指offer Ⅱ024.反转链表
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while(cur != null){
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
剑指offer Ⅱ026.重排链表
解题思路:
- 将链表从中间截断
根据快慢指针将链表截断 - 反转后半段链表
- 再将两个链表合并
class Solution {
public void reorderList(ListNode head) {
if(head == null) return;
//1. 将链表从中间截断
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//mid是后半段链表的头节点
ListNode mid = slow.next;
ListNode cur1 = head;
slow.next = null;//截断链表
//2. 反转后半段链表
ListNode pre = null;
ListNode cur2 = mid;
ListNode tmp = null;
while(cur2 != null){
tmp = cur2.next;
cur2.next = pre;
pre = cur2;
cur2 = tmp;
}
//3. 合并两个链表
//pre 就是后半段链表反转后的头节点
while(pre != null){
//随时更新前半段链表下一个节点的指向
ListNode res = cur1.next;
//合并称为新的链表
//新的链表头节点即是原来链表的头节点, 即cur1
//新链表的头节点 cur1 的下一个节点就是后半段链表的头节点, 即pre
cur1.next = pre;
//更新cur1和pre
cur1 = cur1.next;
pre = pre.next;
//新链表中cur1的下一个节点就是前半段链表的第二个节点, 即res
//以此类推
cur1.next = res;
//更新cur1
cur1 = cur1.next;
}
}
}



