> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/linkedlistff0c_lian_biao/69-_linkedlistff0c_lian_biao_ji_chu.md).

# 6/9, LinkedList，反转与删除

## 6/9, LinkedList，链表基础，反转与删除

写了这么久奇形怪状的数据结构，终于开始灌水了。。哈哈哈哈

### LinkedList 常用操作：

* 翻转
* 找 kth element
* partition
* 排序
* 合并

### 常用技巧：

* dummy node
* 快慢指针
* 多个 ptr 

### [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)

这种 swap 中有个很有意思的性质，如果下一行的等号左面等于上一行的等号右边，并且以第一行的等号左边结尾，那最后实际做的事情是 swap 了第一行等号右，和最后一行等号左。

```java
public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}
```

### [Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/)

#### 这题还挺 tricky 的，写了好几次。

![](/files/-MUt7afwpPZKnk8UNAB8)

```java
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == n) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode cur = head;

        for(int i = 0; i < m - 1; i++){
            prev = prev.next;
            cur = cur.next;
        }

        for(int i = 0; i < n - m; i++){
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }


        return dummy.next;
    }
}
```

### [Remove Nth Node From End of List ](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

### 涉及链表删除操作的时候，稳妥起见都用 dummy node，省去很多麻烦。因为不一定什么时候 head 就被删了。

```java
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }

        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;
        return dummy.next;
    }
}
```

## [Remove Linked List Elements](https://leetcode.com/problems/remove-linked-list-elements/)

这题完全是一个道理，只不过注意下没准要删除的元素是连续的，那种情况下不要动 head.

```java
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while(head.next != null){
            if(head.next.val == val){
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }

        return dummy.next;
    }
}
```

## [Delete Node in a Linked List](https://leetcode.com/problems/delete-node-in-a-linked-list/)

这题稍微有点怪，因为没有 prev 指针，其实只能把后边的值都给 shift 过来。。。

既然是删除，还是用 dummy node.(不然会有 bug，\[0]-->\[1] 删 \[0] 会返回 \[1]-->\[1] 而不是 \[1])

```java
public class Solution {
    public void deleteNode(ListNode node) {
        ListNode dummy = new ListNode(0);
        dummy.next = node;
        while(node.next != null){
            dummy.next.val = node.next.val;
            dummy = dummy.next;
            node = node.next;
        }
        dummy.next = null;
    }
}
```