学步园

Swap Nodes in Pairs:

Given a linked list, swap every two adjacent nodes and return its head.

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.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#define LN ListNode
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        LN Guard(-1);
	    Guard.next=head;
	    LN* pre=&Guard;
	    LN* p1st;
	    LN* p2nd=&Guard;
	    do
	    {
		    p2nd=p2nd->next;
		    if( p2nd==NULL || p2nd->next==NULL ) //注意后面个条件
			    break;
		    p2nd=p2nd->next;
		    LN* tmp=p2nd->next;
		    p1st=pre->next;
		    pre->next=p2nd;
		    p2nd->next=p1st;
		    p1st->next=tmp;
		    pre=p2nd=p1st;
	    }while(1);
	    return Guard.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

最近发现经常用do- while了，呵呵

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#define LN ListNode
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (!head || k<=0)
		    return head;
	    LN* guard=new LN(-1);
	    guard->next=head;
	    LN* pre=guard;
	    LN* pKth=guard;
	    do
	    {
		    for(int i=0;i<k;i++)
		    {
			    if (!pKth)
				    break;
			    pKth=pKth->next;
		    }
		    if ( !pKth )
			    break;
		    _reverse(pre,pKth);
	    }while(1);
	    LN* ans=guard->next;
	    delete guard;
	    guard=0;
	    return ans;
    }
    
    void _reverse(LN*& pre,LN*& pKth)
    {
	    LN* pFirst=pre->next;
	    LN* pTail=pKth->next;
	    LN* pCur=pre->next;
	    pre->next=pTail;
	    pKth->next=NULL;
	    while(pCur)
	    {
		    LN* pTmp=pCur->next;
		    pCur->next=pre->next;
		    pre->next=pCur;
		    pCur=pTmp;
	    }
	    pre=pKth=pFirst;
    }
};

Rotate List：

Given a list, rotate the list to the right by k places, where k is
non-negative.

For example:

Given 1->2->3->4->5->NULL and k = 2,

return 4->5->1->2->3->NULL.

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        if ( head==NULL)
		    return NULL;
	    int len=getListLength(head);
	    k=k%len;
	    if (k==0)
		    return head;

	    ListNode guard(-1);
	    guard.next=head;
	    ListNode* pTail=head;
	    ListNode* pTailPre= &guard;
	    while(k&&pTail)
	    {
		    k--;
		    pTail=pTail->next;
			pTailPre=pTailPre->next;
	    }

	    ListNode* pKth=head;
	    ListNode* pKthPre=&guard;
	    while(pTail)
	    {
		    pTail=pTail->next;
		    pTailPre=pTailPre->next;
		    pKth=pKth->next;
		    pKthPre=pKthPre->next;
	    }

	    ListNode* tmp =guard.next;
	    guard.next=pKth;
	    pKthPre->next=NULL;
	    pTailPre->next=tmp;
	    return guard.next;
    }

    int getListLength(ListNode* head)
    {
	    int len=0;
	    while(head)
	    {
		    len++;
		    head=head->next;
	    }
	    return len;
    }
};