Biegral Blog

      周末， 小雨， 链表翻一翻。用呵呵哒来表达写这篇博文的心情。

      有一个链表， 翻转前k个结点， 如果n-k < k,  则不翻转后n-k个结点， 否则， 翻转。

#include <iostream>
#include <cassert>
using namespace std;


// 带头节点链表长度存于头节点的iData中
typedef struct node
{
    int iData;
    struct node *pNext;
}Node;


// 打印链表
void print(Node *pHead)
{
	assert(pHead != NULL);

	pHead = pHead->pNext;
	while(pHead != NULL)
	{
		cout << pHead->iData << " ";
		pHead = pHead->pNext;
	}

	cout << " " << endl;
}


// 翻转链表(带头结点)
Node *reverseList(Node *pHead)
{
    assert(NULL != pHead);

    Node *p1 = pHead->pNext;
    Node *p2 = p1;
    pHead->pNext = NULL;  // 不可少
    
    while(p1 != NULL)
    {
        p2 = p1;
        p1 = p1->pNext;
        
        p2->pNext = pHead->pNext;
        pHead->pNext = p2;
    }
    
    return pHead;
}


// 少于k, 则不逆转， 否则翻转
Node *reverseLinkWithK(Node *pHead, int k)
{
    assert(pHead != NULL && k > 0);
    assert(pHead->iData >= 0);

    if(pHead->iData < k)
    {
        return pHead;
    }
    
    if(pHead->iData == k)
    {
        return reverseList(pHead);
    }
    
	
	// 接下来的思路：把链表分为左右两个两个链表, pHead和pRightHead分别是左右链表的头结点指针
    Node *p = pHead->pNext;
    Node *pLeftLast = NULL;    // pLeftLast用于保存左边链表的最后结点
    int i = 0;
    while(p != NULL && i < k)
    {
        pLeftLast = p;
        p = p->pNext;
        i++;
    }
    
    pLeftLast->pNext = NULL;   // 不可少
    
    pLeftLast = pHead->pNext;  
    pHead = reverseList(pHead);
    
    int nRight = pHead->iData - k;
    pHead->iData = k;
    
    Node *pRightHead = (Node *)malloc(sizeof(Node));
    assert(pRightHead != NULL);
    
    pRightHead->iData = nRight;
    pRightHead->pNext = p;     // 右边链表已经形成
    
    if(nRight >= k) 
    {
       pRightHead = reverseList(pRightHead);   // 翻转右边链表
    }
    
    pLeftLast->pNext = pRightHead->pNext;      // 左右链表再次相连
    pHead->iData += nRight;
    
    free(pRightHead);
    
    pRightHead = NULL;
    
    return pHead;
}


int main()
{
	// 带头结点的链表
    Node n, n1, n2, n3, n4, n5, n6;
	n.iData = 6;
	n1.iData = 1;
	n2.iData = 2;
	n3.iData = 3;
	n4.iData = 4;
	n5.iData = 5;
	n6.iData = 6;

	n.pNext = &n1;
	n1.pNext = &n2;
	n2.pNext = &n3;
	n3.pNext = &n4;
	n4.pNext = &n5;
	n5.pNext = &n6;
	n6.pNext = NULL;

	print(&n);

	Node *p = reverseLinkWithK(&n, 3);
	print(p);
	
    return 0;
}

        结果：

1 2 3 4 5 6
3 2 1 6 5 4

       没什么好说的。