1->2->3->3->4->4->5, return 1->2->5.1->1->1->2->3, return 2->3.
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = head;
ListNode pre = dummy;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) {
int val = cur.val;
while (cur != null && cur.val == val) {
cur = cur.next;
}
pre.next = cur;
} else {
pre = pre.next;
cur = cur.next;
}
}
return dummy.next;
}
}
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
while (head.next != null && head.next.next != null){
if (head.next.val == head.next.next.val){
int val = head.next.val;
while (head.next != null && head.next.val == val){
head.next = head.next.next;
}
} else {//注意一定要在else语句里head往下传递 否则会溢出
head = head.next;
}
}
return dummy.next;
}
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
1 -> 2 -> 3 -> 4-> 5 -> 6 ->null变为1 -> 5 -> 4 -> 3-> 2 -> 6 ->null
翻转m--n, 不仅要把m-n转好， preMnode. next 要指向n， m.next 要指向postNnode
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (m > n || head == null){
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
for (int i = 1; i < m; i++){
head = head.next;
}
ListNode preM = head;
ListNode mNode = head.next;
ListNode nNode = mNode;
ListNode postN = mNode.next;
for (int i = m; i < n; i++){
ListNode tem = postN.next;
postN.next = nNode;
nNode = postN;
postN = tem;
}
preM.next = nNode;
mNode.next = postN;
return dummy.next;
}
}
prev -> next = prev -> next -> next 即可。但是由于链表表头可能在这个过程中产生变化，导致我们需要一些特别的技巧去处理这种情况。就是下面提到的 Dummy Node。
ListNode fast = head;
ListNode slow = head;
while (fast!= null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
*fast、*slow 都指向单链表的头节点，其中*fast的移动速度是*slow的2倍，当*fast指向末尾节点的时候，slow正好就在中间了。*fast、*slow 都指向单链表的头节点，其中 *fast的移动速度是*slow的2倍。如果 *fast = NULL，说明该单链表 以 NULL结尾，不是循环链表；如果 *fast = *slow，则快指针追上慢指针，说明该链表是循环链表。1 and 0 respectively in the grid.[ [0,0,0], [0,1,0], [0,0,0] ]
2.时间O(m*n) 空间O(m*n)在第i个位置上设置一个障碍物后，说明位置i到最后一个格子这些路都没法走 为0所以说明，在初始条件时，如果一旦遇到障碍物，障碍物后面所有格子的走法都是0再看求解过程，当然按照上一题的分析dp[i][j] = dp[i-1][j] + dp[i][j-1] 的递推式依然成立.碰到了障碍物，那么这时的到这里的走法应该设为0，因为机器人只能向下走或者向右走，所以到这个点就无法通过。
public class Solution {
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int [][] sum = new int [m][n];
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] != 1) {
sum[i][0] = 1;
} else {
break;//后面所有的都无法到达所以break
}
}
for (int j = 0; j < n; j++) {
if (obstacleGrid[0][j] != 1) {
sum[0][j] = 1;
} else {
break;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] != 1) {
sum[i][j] = sum[i-1][j] + sum[i][j-1];
} else {
sum[i][j] = 0;
}
}
}
return sum[m-1][n-1];
}
}
ublic class Solution {
public int totalNQueens(int n) {
int[] res = new int[1];
if (n <= 0) {
return res[0];
}
int[] column = new int[n];
helper(res, column, n, 0);
return res[0];
}
public void helper(int[] res, int[] column, int n, int pos) {
if (pos == n) {
res[0]++;
} else {
for (int i = 0; i < n; i++) {
column[pos] = i;
if (isValid(column, pos)) {
helper(res,column, n, pos + 1);
}
}
}
}
public boolean isValid(int[] column, int pos) {
for (int i = 0; i < pos; i++) {
if (column[i] == column[pos] || Math.abs(column[i] - column[pos]) == pos - i) {
return false;
}
}
return true;
}
}
if ( i != pos && num[i] == num[i - 1]) { continue; }用这个方法防止重复。
if ( i != pos && num[i] == num[i - 1]) { continue; }对于每次从0开始扫的情况：
if (i > 0 && num[i] == num[i - 1] && !visit[i - 1]){ continue; // important: if previous number have same value as (i)th // but have never been visited, then skip current number }
{1,#,2,3}, 1
\
2
/
3
[3,2,1].public class Solution { public ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<Integer>(); if (root == null){ return result; } ArrayList<Integer> left = postorderTraversal(root.left); ArrayList<Integer> right = postorderTraversal(root.right); result.addAll(left); result.addAll(right); result.add(root.val); return result; } } public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } helper(res, root); return res; } public void helper(List<Integer> res, TreeNode root) { if (root == null) { return; } helper(res, root.left); helper(res, root.right); res.add(root.val); } } public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } TreeNode pre = null; Stack<TreeNode> stack = new Stack<TreeNode>(); while (root != null || !stack.isEmpty()) { if (root != null) { stack.push(root); root = root.left; } else { TreeNode peak = stack.peek(); if (peak.right != null && pre != peak.right) {///如果当前栈顶元素的右结点存在并且还没访问过（也就是右结点不等于上一个访问结点）就访问右结点 / root = peak.right; } else {////如果栈顶元素右结点是空或者已经访问过，那么说明栈顶元素的左右子树都访问完毕 需要把栈顶元素加入结果并且回溯上一层 stack.pop(); res.add(peak.val); pre = peak; } } } return res; } }