将链表L就地逆置，即利用原表各结点的空间实现逆置

一、题目

将链表L就地逆置，即利用原表各结点的空间实现逆置。

二、思路

在链表的第二个元素开始执行逆置，因为如果链表只有一个元素，那么逆置就没有意义了。

步骤：

• 假设原链表如下：

  
  原链表@author H_JJia

• 将结点1的指针指向结点3，也就是说将结点2脱离链表：

  
  将结点1的指针指向结点3
  此时结点2脱离链表，变成游离态@author H_JJia

• 将L链表的头结点指针指向结点2，然后结点2变成第一个元素，结点2的指针指向结点1，此刻实现了第一个逆置。

  
  头结点指针指向结点2，结点2的指针指向结点1@author H_JJia
  实现了第一个倒置@author H_JJia

• 重复上述2、 3步，将结点3脱离链表，然后就可以接到头结点之后，变成第一个元素。

  
  结点3接到头结点之后@author H_JJia
  这里写图片描述@author H_JJia

• 结点4依旧是重复步骤2 、 3，将结点4接到头结点之后；

  
  @author H_JJia
  @author H_JJia

• 重复循环，就可以将结点元素实现逆置了。具体代码见下：

四、具体代码

    /*
     * 逆置链表L
     */
    public void convert_List(Node L){
        Node p,t;
        p=L.next;               //此时指针p指向链表L的第一个结点
        while(p.next!=null){    //第二个结点不为空，因为逆置，需要链表有两个及以上的元素逆置才有意义
            t=p.next;
            p.next=t.next;      //此时跳过了t结点元素，也就是说t结点元素脱离了链表
            t.next=L.next;      //将t结点元素放在头结点后面，即t结点元素成为第一个结点
            L.next=t;           //头结点的指针指向t
        }
    }

五、总结

• t=p.next; p.next=t.next; t.next=L.next; L.next=t;
  这几步看着会非常晕的，但是如果照着图看，或者自己画画图，就能够很容易理解了。

• while(p.next!=null)
  原先p已经指向第一个结点，现在p.next!=null 表示需要第二个结点不为空，链表逆置从第二个元素开始。