剑指Offer之Java算法习题精讲链表与二叉树专项训练

/**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode() {}

  *     ListNode(int val) { this.val = val; }

  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

  * }

  */

class Solution {

     public ListNode reverseList(ListNode head) {

         ListNode pre,cur,nxt;

         pre = null ;

         cur = head;

         nxt = head;

         while (cur!= null ){

             nxt = cur.next;

             cur.next = pre;

             pre = cur;

             cur = nxt;

         }

         return pre;

     }

}

/**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode() {}

  *     ListNode(int val) { this.val = val; }

  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

  * }

  */

class Solution {

     public ListNode reverseKGroup(ListNode head, int k) {

          if (head == null ) return null ;

          ListNode a, b;

          a = b = head;

          for ( int i = 0 ; i < k; i++) {

             if (b == null ) return head;

              b = b.next;

          }

          ListNode newHead = reverse(a, b);

          a.next = reverseKGroup(b, k);

          return newHead;

     }

     ListNode reverse(ListNode a, ListNode b) {

         ListNode pre,cur,nxt;

         pre = null ;

         cur = a;

         nxt = a;

         while (cur!=b){

             nxt = cur.next;

             cur.next = pre;

             pre = cur;

             cur = nxt;

         }

         return pre;

     }

}

/**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode() {}

  *     ListNode(int val) { this.val = val; }

  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

  * }

  */

class Solution {

     ListNode left;

     public boolean isPalindrome(ListNode head) {

         left = head;

         return traverse(head);

     }

     boolean traverse(ListNode right){

         if (right == null ) return true ;

         boolean res = traverse(right.next);

         res = res && (right.val == left.val);

         left = left.next;

         return res;

     }

}

/**

  * Definition for a binary tree node.

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode() {}

  *     TreeNode(int val) { this.val = val; }

  *     TreeNode(int val, TreeNode left, TreeNode right) {

  *         this.val = val;

  *         this.left = left;

  *         this.right = right;

  *     }

  * }

  */

class Solution {

     public TreeNode invertTree(TreeNode root) {

         if (root== null ){

             return null ;

         }

         TreeNode lf = invertTree(root.left);

         TreeNode rg = invertTree(root.right);

         root.left = rg;

         root.right = lf;

         return root;

     }

}

/*

// Definition for a Node.

class Node {

     public int val;

     public Node left;

     public Node right;

     public Node next;

     public Node() {}

     public Node(int _val) {

         val = _val;

     }

     public Node(int _val, Node _left, Node _right, Node _next) {

         val = _val;

         left = _left;

         right = _right;

         next = _next;

     }

};

*/

class Solution {

     public Node connect(Node root) {

         if (root== null ) return null ;

         method(root.left,root.right);

         return root;

     }

     public void method(Node left,Node right){

         if (left == null || right == null ) {

             return ;

         }

         left.next = right;

         method(left.left,left.right);

         method(right.left,right.right);

         method(left.right,right.left);

     }

}

/**

  * Definition for a binary tree node.

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode() {}

  *     TreeNode(int val) { this.val = val; }

  *     TreeNode(int val, TreeNode left, TreeNode right) {

  *         this.val = val;

  *         this.left = left;

  *         this.right = right;

  *     }

  * }

  */

class Solution {

     public void flatten(TreeNode root) {

         if (root == null ) return ;

         flatten(root.left);

         flatten(root.right);

         TreeNode left = root.left;

         TreeNode right = root.right;

         root.left = null ;

         root.right = left;

         TreeNode p = root;

         while (p.right != null ) {

             p = p.right;

         }

         p.right = right;

     }

}