Linked List专题二(cc charpter2)

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

分析

1.链表反转：

给一个单向链表，把它从头到尾反转过来。比如： a -> b -> c ->d 反过来就是 d -> c -> b -> a 。

这里讲解两种方法：

第一种方法就是把每个Node按照顺序存入到一个stack里面，这样，最后面一个就在最上面了。然后，把每一个再取出来，这样顺序就换过来了。

public static ListNode reverselist(ListNode head){

  Stack<ListNode> stack=new Stack<ListNode>();

  if(head==null||head.next==null){

  return head;

  }

  while(head.next!=null){

  stack.push(head);

  head=head.next;

  }

  ListNode current=stack.pop();

  ListNode a=current;

  while(!stack.empty()){ 

  ListNode nextpoint=stack.pop();

  current.next=nextpoint;    

  current=nextpoint;

  }

  current.next=null;//非常重要，最后一个指针指向null！！！！！

  return a;

  }

2.用两个指针

第二种方法就是利用两个指针，分别指向前一个节点和当前节点，每次做完当前节点和下一个节点的反转后，把两个节点往下移，直到到达最后节点。

 public static ListNode reverselist2(ListNode pre){

       

        ListNode last=pre;

        ListNode cur=pre.next;

        while(cur!=null){

            last.next=cur.next;

            cur.next=pre;

            pre=cur;

            cur=last.next;

        }

        return pre;

    }

test!!

package Linkedlist;

import java.util.Stack;

public class test {
     public static ListNode reverselist(ListNode head){
           Stack<ListNode> stack=new Stack<ListNode>();
           if(head==null||head.next==null){
               return head;
           }
           while(head.next!=null){
               stack.push(head);
               head=head.next;
           }
           ListNode current=stack.pop();
           ListNode a=current;
           while(!stack.empty()){ 
               ListNode nextpoint=stack.pop();
               current.next=nextpoint;           
               current=nextpoint;
           }
           current.next=null;//非常重要，最后一个指针指向null！！！！！
           return a;
       }
     public static ListNode reverselist2(ListNode pre){
           
            ListNode last=pre;
             ListNode cur=pre.next;
            while(cur!=null){
                last.next=cur.next;
                cur.next=pre;
                pre=cur;
                cur=last.next;
            }
            return pre;
        }
    
     public static void main(String[] args) {
            // TODO Auto-generated method stub
            ListNode head = new ListNode(0);
            ListNode cur = head;
            for(int i = 1; i < 10; i++){
                ListNode node = new ListNode(i);
                cur.next = node;
                cur = node;
            }

           //  Solution s = new Solution();
            head = reverselist(head);
            print(head);
        }

        static void print(ListNode head){
            while(head != null){
                System.out.println(head.val);
                head = head.next;
            }
        }

}

所以本题用两个指针的方式：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverselist(ListNode pre,ListNode next){
       
        ListNode last=pre.next;
         ListNode cur=last.next;
        while(cur!=next){
            last.next=cur.next;
            cur.next=pre.next;
            pre.next=cur;
            cur=last.next;
        }
        return last;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode newhead=new ListNode(0);
        newhead.next=head;
        ListNode pre=newhead;
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            ListNode next=cur.next;
            if(count==k){
                pre=reverselist(pre,next);
                count=0;
            }
            cur=next;
        }
        
        return newhead.next;
        
    }
}

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

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

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
     public ListNode reverselist(ListNode pre,ListNode next){
         ListNode last=pre.next;
         ListNode cur=last.next;
        while(cur!=next){
            last.next=cur.next;
            cur.next=pre.next;
            pre.next=cur;
            cur=last.next;
        }
        return last;
    }
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null||head.next==null||m==n){
                return head;
            }
            ListNode dummy=new ListNode(0);
            dummy.next=head;
            ListNode h1=dummy;
            
            int i=1;
            for(;i<m;i++){
                h1=h1.next;
            }
            ListNode  h12=h1;
            ListNode cur=h12.next;
            while(cur!=null){
                ListNode mNode=cur.next; 
                if(i==n){
                   h12=reverselist(h12,mNode);
                }
                cur=cur.next;
                i++;
            }
            return dummy.next;
    }
}