Swap Nodes in Pairs

For example, Given `1->2->3->4`, you should return the list as `2->1->4->3`.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

三指针法

代码

``public class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(0);dummy.next = head;// curr是待交换的两个节点前面那个节点ListNode curr = dummy;while(curr != null && curr.next != null && curr.next.next != null){ListNode third = curr.next.next.next;ListNode second = curr.next.next;ListNode first = curr.next;// 把第二个节点的next置为第一个节点second.next = first;// 把当前节点的next置为第二个节点curr.next = second;// 把第一个节点的next置为第三个节点first.next = third;// 将当前节点置为第一个节点，继续下一轮交换（此时first实际已经是第二个节点了）curr = first;}return dummy.next;}}``

``public class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode curr = dummy;while(curr != null && curr.next != null && curr.next.next != null){ListNode tmp = curr.next.next.next; // tmp - 3curr.next.next.next = curr.next;// 3 - 1curr.next = curr.next.next; // 1 - 2curr.next.next.next = tmp; // 3 - tmpcurr = curr.next.next; // 0 - 2}return dummy.next;}}``

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example, Given this linked list: `1->2->3->4->5`

For `k = 2`, you should return: `2->1->4->3->5`

For `k = 3`, you should return: `3->2->1->4->5`

分段反转

思路

• 如果剩余节点不足K个则不执行反转，所以要先判断是否可以反转

• 拆分成子函数，清晰易懂

• K等于1的时候直接返回原链表

代码

``public class Solution {public ListNode reverseKGroup(ListNode head, int k) {if(k == 1) return head;ListNode dummy = new ListNode(0);dummy.next = head;ListNode curr = dummy;while(curr != null && curr.next != null && curr.next.next != null){// 检测是否有足够节点供反转，不足直接退出if(!hasEnoughNodes(curr.next, k)) break;// 记录下第一个节点，反转后成为最后一个节点ListNode last = curr.next;// 从这第一个节点开始反转K个节点ListNode[] nodes = reverseK(last, k);// 将第0个节点的next接上新链表的头节点curr.next = nodes[0];// 将新链表的尾节点的后一个节点置为后一段链表的头节点last.next = nodes[1];// 准备反转下一段链表curr = last;}return dummy.next;}private boolean hasEnoughNodes(ListNode runner, int k){int remains = 0;while(runner != null && remains < k){remains++;runner = runner.next;}if(remains < k) return false;return true;}private ListNode[] reverseK(ListNode p1, int k){ListNode p2 = p1.next;// 反转K个节点while(p2 != null && k > 1){ListNode tmp = p2.next;p2.next = p1;p1 = p2;p2 = tmp;k--;}// 返回值第一个是新的链表头节点，第二个是下一段链表的头节点ListNode[] res = {p1, p2};return res;} }``