Day08——链表专题

冷不防 2024-04-03 12:40 62阅读 0赞

#### 文章目录 ####

*   *   *  16.反转链表
         *  17.两两交换链表中的节点

--------------------

#### 16.反转链表 ####

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，因为开始反转的时候cur->next就改变值了。

接下来，就是循环走如下代码逻辑了，继续向后移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

**指向谁 就等于谁**

**代码实现：**

//双指针
    class Solution {
        
           public ListNode reverseList(ListNode head) {
        
            ListNode pre = null;
            ListNode cur = head;
            ListNode temp = null;
            while (cur!=null){
        
                temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            return pre;
        }
    }

// 递归 
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            return reverse(null, head);//将prev置为null，cur置为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);// prev = cur; cur = temp;
        }
    }

#### 17.两两交换链表中的节点 ####

1.如下图所示:

先将cur虚拟头节点指向节点2，其次节点2指向节点1，最后节点1指向节点3，**交换链表之前将节点1和节点3用临时节点记录**，之后完成步骤一二三，第一轮交换完成后，**cur往后移动二位，准备下一轮交换**，最后返回cur.next即头节点。

![image-20221014201154519][]

![image-20221014203832850][]

**代码实现：**

//虚拟头节点
    class Solution {
        
     public ListNode swapPairs(ListNode head) {
        
            ListNode dummy = new ListNode(0);//设置一个虚拟头节点
            dummy.next = head;//将虚拟头节点指向head，这样方便后续操作。
            ListNode cur = dummy;//用cur临时指针来代替虚拟头节点
         
            while(cur.next!=null&&cur.next.next!=null){
        //分别排除偶数和奇数
                ListNode temp = cur.next;//记录临时节点
                ListNode temp1 = cur.next.next.next;//记录临时节点
                
                cur.next = cur.next.next;//步骤一
                cur.next.next = temp;//步骤二
                temp.next = temp1;//步骤三
                
                cur = cur.next.next;//cur移动两位，准备下一轮交换
            }
            return dummy.next;//返回头节点
        }
    }

// 递归版本
    class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
            // base case 退出提交
            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;
        }
    }

[image-20221014201154519]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/154e84682ad64476b88f7f78b27988f9.png
[image-20221014203832850]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f70f8655cd14489cae029e61572d5f3c.png