反转链表

link：206. 反转链表 - 力扣（LeetCode）

思路分析

与数组不同，链表没必要定义新的链表进行存储【对内存空间的浪费】
直接改变next指针即可.
注意头节点指向的下一个节点为null

双指针法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode reverseList(ListNode head) {
        //双指针操作 
        ListNode prev = null;
        ListNode cur = head;
        //记录节点
        ListNode temp = null;
        while(cur != null) {
            temp = cur.next;//保存下一个节点
            cur.next = prev;
            //赋值之后整体向后移动
//注意先移动prev 不如cur已经移动后记录不到prev新的位置
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}
递归法

和双指针法是一样的逻辑【升华版】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode reverseList(ListNode head) {
      //prev -> null 初始化 head反转的第一个节点 启动反转操作
        return reverse(null, head);
    }
    private ListNode reverse(ListNode prev, ListNode cur) {
        if(cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;
        cur.next = prev;
        //更新prev和cur的位置
        return reverse(cur,temp);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//从后向前递归
class Solution{
    ListNode reverseList(ListNode head) {
        //边缘条件判断
        if(head == null) return null;
        if(head.next == null) return head;

        //递归调用 翻转头节点之后的链表
        ListNode last = reverseList(head.next);
        //翻转头节点之后链表的指向
        head.next.next = head;
        //此时的head节点为尾节点, next需要指向null
        head.next = null;  
        return last;
    }
}
两两交换链表中的节点

link：24. 两两交换链表中的节点 - 力扣（LeetCode）

思路分析

注意在交换之前要先存储需要的值

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        //进行递归
        ListNode newNode = swapPairs(next.next);

        //交换
        next.next = head;
        head.next = newNode;

        return next;
    }
}
虚拟头节点

img

我们想实现的是1和2交换，3和 4交换，此时很难不想到借用中间变量实现，不用递归实现【每次单独处理头节点】更优雅.
注意5后面是空指针就不用交换
判断next.next不为空是为了防止空指针异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

    while (prev.next != null && prev.next.next != null) {
      ListNode temp = head.next.next; // 缓存 next
      prev.next = head.next;          // 将 prev 的 next 改为 head 的 next
      head.next.next = head;          // 将 head.next(prev.next) 的next，指向 head
      head.next = temp;               // 将head 的 next 接上缓存的temp
      prev = head;                    // 步进1位
      head = head.next;               // 步进1位
    }
    return dummy.next;
    }
}