最少变量进行链表逆置,怕忘存档

基本思路

简单的思路,就是首先交换 root->nextrevert_root 的指向,此时已经逆置了一个元素

但是 rootrevert_root 就反了,再交换下就 ok 了

直接上代码

/*
        Author: SpringHack - springhack@live.cn
        Last modified: 2019-04-02 01:32:40
        Filename: main.c
        Description: Created by SpringHack using vim automatically.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Test data
int test_data[] = {
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10
};

// Node struct
typedef struct _node {
  int value;
  struct _node* next;
} node_item;
// Just easy to use malloc
typedef node_item* node;

// Define linked list root and reverted linked list root
// Only two variables needed to revert a linked list
static node root = NULL;
static node revert_root = NULL;

int main() {
  // Create linked list
  {
    int i = 0, count = sizeof(test_data) / sizeof(int);
    node tmp;
    while (i < count) {
      if (!root) {
        root = (node)malloc(sizeof(node_item));
        tmp = root;
      } else {
        tmp->next = (node)malloc(sizeof(node_item));
        tmp = tmp->next;
      }
      tmp->next = NULL;
      tmp->value = test_data[i];
      ++i;
    }
  }
  // Print linked list
  {
    node tmp = root;
    while (tmp) {
      printf(tmp->next ? "%d " : "%d", tmp->value);
      tmp = tmp->next;
    }
    printf("\n");
  }
  // Revert linked list
  {
    while (root) {
      if (!revert_root) {
        revert_root = root;
        root = root->next;
        revert_root->next = NULL;
      } else {
        revert_root = (node)((intptr_t)revert_root ^ (intptr_t)root->next);
        root->next = (node)((intptr_t)revert_root ^ (intptr_t)root->next);
        revert_root = (node)((intptr_t)revert_root ^ (intptr_t)root->next);
        revert_root = (node)((intptr_t)revert_root ^ (intptr_t)root);
        root = (node)((intptr_t)revert_root ^ (intptr_t)root);
        revert_root = (node)((intptr_t)revert_root ^ (intptr_t)root);
      }
    }
  }
  // Print reverted linked list
  {
    node tmp = revert_root;
    while (tmp) {
      printf(tmp->next ? "%d " : "%d", tmp->value);
      tmp = tmp->next;
    }
    printf("\n");
  }
  return 0;
}

本文链接:

https://www.dosk.win/2019/04/02/42.html
1 + 1 =
2 评论
    sz Chrome 73 OSX
    5月3日 回复

    revert_root = (node)((intptr_t)revert_root ^ (intptr_t)root->next);

        root->next = (node)((intptr_t)revert_root ^ (intptr_t)root->next);
        revert_root = (node)((intptr_t)revert_root ^ (intptr_t)root->next);
        revert_root = (node)((intptr_t)revert_root ^ (intptr_t)root);
        root = (node)((intptr_t)revert_root ^ (intptr_t)root);
        revert_root = (node)((intptr_t)revert_root ^ (intptr_t)root);
     

    这里只是交换了节点,没有滚动前进,那么while循环岂不是一直在处理前3个node节点?
    看的出代码的核心思想是交换ab的值:
    a = a^b
    b = a^B
    a = a^B
    而且看代码前3个节点1->2->3交换后为3->2 (rev node 为1),那么下一次交换,如何能把第四个节点交换到第一位去呢(如1234,第一次交换为324(rev为1),那么下一次4如何与3交换?),以此类推,每次新交换一个节点都需要把前面的所有节点都交换一次?
    尝试运行了代码,走不通,等待解答。
    error: ‘intptr_t’ undeclared (first use in this function)

        revert_root = (node)((intptr_t)revert_root ^ (intptr_t)root->next);
      sz Chrome 73 OSX
      5月3日 回复

      @sz 为什么回复中会变为白色背景?没办法修改回答,额,,so sad