l链表的反转

对于链表的反转：1.整个序列链表进行翻转，不借用额外的空间 2.链表中k个序列进行链表的翻转

对于整个序列进行翻转过程，使用三个指针，pre，cur，temp；cur指针保存每一次在翻转过后的头部指针。

 1 public void reverse(ListNode head)
 2     {
 3         ListNode pre=head;
 4         ListNode cur=head;
 5         ListNode temp;
 6         while(pre.next!=null)
 7         {
 8             temp=pre.next;
 9             pre.next=temp.next;
10             temp.next=cur;
11             cur=temp;
12         }
13          PrintListNode(cur);
14         
15               return cur
16     }

2. 链表中K个序列进行翻转过程：

1.某个结点之后的链表进行的翻转：1-2-3-4---->1-4-3-2

 1 public ListNode reverse1(ListNode head)
 2     {
 3         ListNode pre=head.next;
 4         while(pre.next!=null)
 5         {
 6             ListNode cur=pre.next;
 7             pre.next=cur.next;
 8             
 9             cur.next=head.next;
10             head.next=cur;
11         }
12         PrintListNode(head);
13         return head;
14     }

2. K个序列进行翻转：tail结点标记K 个序列最终点，同时要head记录K个结点的首字结点。

 1 public ListNode inverse1(ListNode head,int k)
 2      {
 3          /*空间复杂度为1，reverse时候对特定中间区域进行翻转*/
 4          if(k < 2|| head.next==null) 
 5              return head;
 6        ListNode dummy=new ListNode(-1);
 7        
 8        dummy.next=head;
 9        
10        ListNode tail=dummy,pre=dummy,temp;
11        int count;//记录最后K子序列的点
12        
13        while(true)
14        {
15            count=k;
16            while(count>0 && tail!=null)
17            {
18                //找到其中满足K序列的位置
19                count--;
20                tail=tail.next;
21            }
22            if(tail==null)
23                break;
24            
25            head=pre.next;
26            
27            //进行序列翻转,保持整个序列连贯性
28            while(pre.next!=tail)
29            {
30                temp=pre.next;
31                pre.next=temp.next;
32                //k=4 tai=4 -1-1-2-3-4-5-6---4-3-2-1-5-6 这里head是在1位置
33                temp.next=tail.next;
34                tail.next=temp;
35            }
36            // 翻转之后序列：-1-4-3-2-1-5-6
37            tail=head;//ba保持不变
38            pre=head;
39            
40        }
41       return dummy.next ;
42        
43       }