反转链表 - 高飞网
616 人阅读

反转链表

2017-07-28 02:09:46

    定义一个函数,输入一个链表的头结点,反转该链表并输出反转后的链表的头结点。链表定义如下:

struct Node
{
    int data;
    struct Node *pNext;
}

    为了正确的反转一个链表,需要调整链表中指针的方向。为了将调整指针这个复杂的过程分析清楚,可以借助图形来直观地分析。在下图(a)所示的链表中,h、i和j是3个相邻的结点。假设经过若干操作,已经把结点h之前的指针调整完毕,这些结点的pNext都指向前面一个结点。接下来把i的pNext指向h,此时的链表结点如(b)图示。

    注:(a)一个链表。(b)把i之前所有的结点的pNext都指向前一个结点,导致链表在结点i、j之间断裂。

    不难看到,由于结点i的pNext指向了它的前一个结点,导致我们无法在链表中遍历到结点j。为了避免链表在i处断开,需要在调整结点i的pNext之前,把结点j保存下来。

    也即在调整结点i的pNext指针时,除了需要知道结点i本身之外,还需要i的前一个结点h,因此需要把结点i的pNext指向结点h。同时还事先需要保存i的下一结点j,以防止链表断开。因此相应地我们要定义3个指针,分别指向当前遍历到的结点、它的前一个结点和后一个结点。

    程序要注意以下3个问题:

  1. 输入的链表头指针为NULL或整个链表只有一个结点时,程序不能崩溃。
  2. 反转后的链表不能断裂
  3. 返回的反转之后的头结点应为原始链表的尾结点。

java代码实现

public Link reverse(){
    Link link = new Link();//新的反转链表
    Node pNode = head.next;//移动指针指向第一个结点
    Node pPrev = null;//下个节点的后继
    while(pNode!=null){
	Node pNext = pNode.next;//把下一个结点临时保存,避免断开                
        if(pNext==null){//到尾结点了
	    link.head.next= pNode;
	}
	pNode.next=pPrev;//当前的后继反转向前
	pPrev = pNode;//把当前结点作为下一次的头结点
	pNode = pNext;
    };
    return link;
}


还没有评论!
54.196.5.6