Reverse Nodes In K Group,将链表每k个元素为一组进行反转—特例Swap Nodes in Pairs,成对儿反转

问题描述:1->2->3->4,假设k=2进行反转,得到2->1->4->3;k=3进行反转,得到3->2->1->4

算法思想:基本操作就是链表反转,将k个元素当作滑动窗口,依次进行反转。

 public class ReverseNodesInKGroup {     public ListNode reverseKGroup(ListNode head, int k) {         if (k == 1 || head == null || head.next == null)             return head;         ListNode first = head, last = head;         ListNode preHead = new ListNode(-1);         preHead.next = head;         ListNode preGroup = preHead, nextGroup = preHead;         int count = 1;         while (last != null)         {             if (count != k)             {                 last = last.next;                 count++;             }             else             {                 nextGroup = last.next;                 reverseList(first, last);// 节点反转后,first <- ... <-clast                 preGroup.next = last;// 前面转换过的组连接到新的组,pregrou记录prehead,最后返回prehead                 preGroup = first;                 first.next = nextGroup;                 first = nextGroup;                 last = nextGroup;                 count = 1;             }         }         return preHead.next;     }     //基本反转操作     private void reverseList(ListNode head, ListNode tail) {         ListNode pre = new ListNode(-1), node = head;         pre.next = head;         while (pre != tail) {             ListNode temp = node.next;             node.next = pre;             pre = node;             node = temp;         }     } }

特例Swap nodes in pairs

问题描述:给一序列,交换每相邻的两个元素,并返回头结点。例如:1-2-3-4   返回序列2-1-4-3

算法思路:除了第一组元素,其他每次交换一对儿元素,要改变四个指针。所以,定义四个指针。其中只有两个指针是不想关,其他依赖这两个指针。

方法一:

 public ListNode swapPairs(ListNode head) {         if(head == null || head.next == null)            {                return head;            }         ListNode pPre = new ListNode(0);         pPre.next = head;         ListNode p1 = head;         ListNode p2 = null;         ListNode pNext = null;         ListNode temp = null;         while(p1!= null && p1.next != null)         {             p2 = p1.next;             if(p1 == head)             {                 temp = p2;             }             pNext = p2.next;             p2.next = p1;             p1.next = pNext;             pPre.next = p2;             pPre = p1;             p1 = pNext;         }         return temp;     }

方法二:

public static ListNode swapPairs(ListNode head) {        ListNode pPrepre = null;  //节点对的前前元素        ListNode pPre = null;     //节点对的前一个元素,依赖p        ListNode p = head;        //要移动的节点对的第一个元素        ListNode pNext = null;    //节点对的第二个元素,依赖p        while (p != null && p.next != null) {            pPre = p;            p = p.next;            pNext = p.next;            if (pPre == head) {                head = p;            }            if (pPrepre != null) {                pPrepre.next = p;            }            p.next = pPre;            pPre.next = pNext;            pPrepre = pPre;//其他元素都依赖p,但pPrepre不依赖p,所以每次移动pPrepre和p            p = pNext;        }        return head;    }