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];
}
}