369. Plus One Linked List

• reverse, add, reverse
• dfs return carry
• two points to the change part

  	/**
  	* Definition for singly-linked list.
  	* public class ListNode {
  	* int val;
  	* ListNode next;
  	* ListNode(int x) { val = x; }
  	* }
  	*/
  	class Solution {
  	public ListNode plusOne(ListNode head) {
  	if (head == null) return null;
  	ListNode pre = null;
  	ListNode cur = head;
  	// reverse linkedlist to the end node
  	while (cur != null && cur.next != null) {
  	ListNode next = cur.next;
  	cur.next = pre;
  	pre = cur;
  	cur = next;
  	}
  	// add one
  	int carry = 1;
  	// reverse back
  	while (pre != null) {
  	cur.val += carry;
  	carry = cur.val / 10;
  	cur.val = cur.val % 10;
  	ListNode beforePre = pre.next;
  	pre.next = cur;
  	cur = pre;
  	pre = beforePre;
  	}
  	if (carry > 0) {
  	cur.val += carry;
  	carry = cur.val / 10;
  	cur.val = cur.val % 10;
  	if (carry > 0) {
  	ListNode newHead = new ListNode(carry);
  	newHead.next = head;
  	head = newHead;
  	}
  	}
  	return head;
  	}
  	}
  	class Solution1 {
  	public ListNode plusOne(ListNode head) {
  	if( DFS(head) == 0){
  	return head;
  	}else{
  	ListNode newHead = new ListNode(1);
  	newHead.next = head;
  	return newHead;
  	}
  	}
  	public int DFS(ListNode head){
  	if(head == null) return 1;
  	int carry = DFS(head.next);
  	int val = head.val + carry;
  	head.val = val%10;
  	return val/10;
  	}
  	}

  view raw 369_1005.java hosted with ❤ by GitHub